Re: JSH: Not obvious? Simple math test.

On Jan 13, 12:58 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Fri, 11 Jan 2008 16:41:10 -0800 (PST), JSH <jst...@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.

Sounds good. Have fun.

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.

Shouldn't matter. It just will not work at all if k is not coprime to
nT.

Thanks,

rossum

Yeah sure, no prob. I'm moving on from the factoring issues to
Diophantine equation solutions that follow from the factoring
congruences, but I'll keep checking this space.

James Harris

.