Re: TI-M: Re: TI-Math Digest V1 #22
[Prev][Next][Index][Thread]
Re: TI-M: Re: TI-Math Digest V1 #22
In a message dated 6/14/00 6:07:13 PM Mountain Daylight Time,
noveck@pluto.njcc.com writes:
> > The point of the congruency list is to cut down on the number of
> divisions,
> > since it's the division (or the check for divisibility as a whole) that
is
> > the slowest process (from my experience). Dividing each potential
> > probable-prime would take the complete point out of wheeler algorithm,
> whose
> > purpose is to decrease the number of overall trial-divisions. If you
have
> to
> > trial-divide potential probable-primes, which, if determined to be not
> > divisible by 2, 3, 5, 7, 11 (or whatever), would then be trial-divided
> into
> > the number, the whole process would be a hell of a lot slower. The
> "trouble"
> > of the congruency list pays off in that probable primes are quickly
> > calculated one after another, so most of the processing time is spent
> finding
> > factors of the inputted number, not determining the divisibility of
> potential
> > probable-primes.
>
> Wait a sec, maybe I get it now - we _don't_ prove the primality of any
other
> those numbers, do we? We trial divide the number to be factored by all the
> PROABABLE primes, not just the PROVEN ones? Or am I still way off? =)
Nope, that's correct (nope as in you're not way off ;) You use your
congruency list to trial-divide by all probable primes, a probable prime
being, in the case of modulus 2310, for example, a whole number not divisible
by 2, 3, 5, 7, or 11, which includes both primes and composite numbers
(although for the most part primes, at least in the beginning). Of course,
this shouldn't be confused with pseudoprimes that pass the Fermat Test, where
if a^(p-1) = 1(mod p) for some base a, then p is *probably prime*.
JayEll