Folks,
I'm just throwing out some number theory division stuff I've
played with over the years hoping it might be of some help to the
project.
Here's one that uses the property illustrated here:
3*7*11 = 231
231 % (3*5) = 6
3 divides the residue 6, therefore 3 is a factor of 231
5 doesn't divide 6, therefore 5 is not a factor of 231
3 and 5 are called primary candidates (vector P1)
So, for the algorithm
step 1: get a large composite
P1_next = 1
do
P1 = P1_next
P1_next *= p1_i
until P1_next > N
step 2: compute residue <- N % P1
Hopefully the residue is significantly smaller than the large
composite
step 3:
either
factor the residue
or
divide residue by each of the members of P1
step 4: any factor of the residue that also appears in P1 is
also a factor of N
here's a thought if the residue is not easily factored due to
size:
given
a large number, N which we wish to factor
a large, but smaller composite number
the residue of N with respect to the composite
if we can somehow choose small, secondary candidates (vector
P2) such that:
N % ( product(P1)*product(P2) ) < minimum_member_of(P1)
then we know that no members of P1 are factors of N
Generally choosing those small candidates might be
computationally as hard as (or exactly equivalent to) factoring
the residue.
Anyone think this is worth more than a cursory look? Anyone know if
this type of approach has already been discounted?
Thanks,
--jim
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
