Re: JSH: Not obvious? Simple math test.

On Fri, 11 Jan 2008 16:41:10 -0800 (PST), JSH <jstevh@xxxxxxxxx>
wrote:

[snip]

Thanks for that. I have now revised my paper algorithm to incorporate
your comments:

James has given three equations:

y = +/- (1+2a^2)^(-1) z mod p (1)

z = (2a)^(-1) * (1 + 2a^2)k mod p (2)

k^2 = ((a^2)+1)^(-1) * (nT) mod p (3)


From these, together with help from James, I have tried to devise a
factoring algorithm.

We are given a T to factor. We pick a, n and p such that (3) will
give us a value for k. We can then use (2) to determine z and (1) to
determine two values for y. We try to find factors by looking at the
gcd of eight possible combinations of z, y and p with T.


Given a T to factor:

1 Set p <- 0, alpha <- 1 (alpha = a in the equations above)

2 Set n <- 0

3 Set n to the next value in the sequence 1, 101, 103, 107, ... (1
followed by odd primes > 100).

4 If p <= sqrt(nT) then pick a new prime p > sqrt(nT).

5 If the RHS of (3) is not a quadratic residue mod p go to step 3.

6 Using (3) determine a value for k. If gcd(k, nT) != 1 then
increment alpha by 1 and go to step 2.

7 Using (2) determine a value for z.

8 Using (1) determine the two values for y: y1 and y2.

9 Try gcd(z+y1, T), gcd(z-y1, T), gcd(z+y1-p, T), gcd(z-y1-p, T),
gcd(z+y2, T), gcd(z-y2, T), gcd(z+y2-p, T), gcd(z-y2-p, T) to see if a
proper factor of T is found. If a proper factor is found then return
it and exit.

10 Increment alpha by one and go to step 2.


Changes from previous version:

1. Allowed values for n have been changed.

2. Rather than fixing n and varying alpha I now have fixed alpha and
vary n to get a quadratic residue mod p at the RHS of equation (3).

3. I recalculate p if required after stepping n.

4. I use the modular version of equation (1) which gives two
possible values for y. I have increased the number of trial gcd's to
eight to use both values for y in the same four ways as in the
previous version.


Question for James:

At step 6, if I find that k is not coprime to nT, do I stick with the
same value of alpha and step n (= "go to step 3") or do I give up on
that alpha and move to the next value (= "increment alpha by 1 and go
to step 2")? Currently I am doing the latter.


Thanks,

rossum

.