TI-M: Re: TI-Math Digest V1 #22
[Prev][Next][Index][Thread]
TI-M: Re: TI-Math Digest V1 #22
> I know Wheeler factorization is a good algorithm for proving/disproving
> primality of numbers by doing a sort of "enhanced" trial-divide. It's
based
> on the fact that, for example, all primes greater than 2*3*5 = 30 are
> congruent to 1, 7, 11, 13, 17, 19, 23, and 29, modulus 30 (I'd have to
look
> that up to confirm that, but I think that list is right). For example, 79
=
> 19 (mod 30), and 293 = 23 (mod 30).
Do you happen to know of a page with the Wheeler factorization algorithm
explained? I suppose Knuth's fast algorithm won't work because it only
determines whether a number is prime to a high degree probability and is not
certain, correct?
> Factoring the "expanded" form of 283^8 * 293^5 would expectedly be very
> quick; it doesn't take long (expecially with Wheeler factorization) to
> trial-divide up to 283, and after that all the factors just "fall into
> place".
Call it a hunch, but I'd imagine trial dividing a 32-digit number by all
primes up through 283 would take more than half a second - especially with
BCD numbers. There must be some other algorithm in there helping to speed
it up, especially since this is finding whether all these numbers are primes
as it goes???
> Likewise, I wouldn't expect the expanded form of 299! to take at all
> long to completely factor, as it has prime factors immediately at 2, and
it's
> biggest prime factor is less than 299. It's almost a shame that it takes
the
> 89 20 seconds to simply divide one number continuously by a few hundred
> numbers (although the original number is quite long); it's that BCD crap,
I
> suspect...
Somehow I don't think you could do it too much better, since we need to use
a 613 digit decimal number and I don't believe that IEEE decimals will cut
it (they don't guarantee full accuracy, correct?) so BCD seems like the way
to go. Of course, the number of digits should decrease rapidly as soon as
we cut out all those factors of 2, 3, etc. . .
-Scott
References: