Re: JSH: Not obvious? Simple math test.

On Jan 10, 2:08 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Wed, 9 Jan 2008 07:38:57 -0800 (PST), JSH <jst...@xxxxxxxxx> wrote:
It has finally occurred to me that some of you may not understand what
I thought was a basic math point, so this post is to check, with a
simple math test:

[snip]

James Harris

JSH - January 2008 Factoring method

James has given three equations:

z^2 = y^2 + nT (1)

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

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


Looks correct. Also nT has to be odd and coprime to 3. In addition k
must be coprime to nT.

Lastly, if you use 'n' for values other than 1 or -1, then you need to
pick large primes if possible, while despite that n=5, as you can't go
smaller, of course, may only block about 50% of the solutions
available, while in general, the equations will work 50% of the time,
so with n=5, they might work only 25% of the time.

From these, together with hints and examples in his blog
(http://mymath.blogspot.com/) I have tried to devise a factoring
algorithm.

Given a T to factor:

1 Set n <- 1

That is best but may not be practical for a large target composite T.

2 Pick a prime p > sqrt(nT)

Usually it should suffice to pick p>sqrt(T), but if n is extremely
large you might go higher, and it shouldn't hurt, nor should it add
appreciably to the calculation times, though it is important that n
not contain a lot of small prime factors.

3 Set alpha <- 1 (alpha = a in the equations above)

Should be ok for a start.

4 Using (3) determine a value for k. This may not be possible if the
RHS of (3) is not a quadratic residue. If so then increment alpha by
1 and repeat this step.

That is probably a bad route, as instead you can simply pick n such
that your choice of alpha will work.

But if n has a lot of small prime factors you probably wouldn't want
to use it.

So there is a balance that has to be found. Note: n cannot be even
and it cannot have 3 as a factor.

5 Using (2) determine a value for z.

6 Using (1) determine a value for y. If y is not an integer then
increment alpha by one and return to step 4.

You can use the following equations to find y:

y = (1+2α^2)^{-1} z mod p, or y = -(1+2α^2)^{-1} z mod p

7 Try gcd(z+y, T), gcd(z-y, T), gcd(z+y-p, T), gcd(z-y-p, T) to see
if a factor of T is found. If a factor is found then return it and

Yes.

exit, if not then increment alpha by one and return to step 4.

Or you can shift n, or you can shift p. It is possible that for a
given p, no solution exists, as that will be true about 50% of the
time based on whether or not:

2^{-1}(x^{-1} z - 1) mod p

is a quadratic residue or not. If it's not, then you won't find
solutions. Note that x = y mod p or -y mod p.

So with T a product of two primes there are just two chances that you
will get a quadratic residue there (hmmm...so better than 50%
factoring! That means 75% probability then?) if n=1.

If n is anything other than 1, then you have more chances as more y's
will exist that non-trivially factor.

So oddly enough, with these factoring congruences you can make
factoring T easier by multiplying it by a large prime! Or primes.

8 When enough values of alpha have failed, then increment n by 1.

No. The last thing you want to do is search for alpha's. Better to
directly force k to be a quadratic residue by just picking some alpha
and then picking an n that will do so, that also hopefully does not
have many small prime factors, which CANNOT have 3 as a factor and
should not be even.

9 If n mod 3 = 0, then increment n by 1. (n % 3 != 0)

Only if that is to get you a quadratic residue for some alpha.

10 Go to step 2.

Questions for James:

1 Is this a correct description of your current method?

I've corrected above.

2 Am I correct to start with n = 1 and alpha = 1?

Probably not. alpha = 1 is ok, but it is unlikely that n=1 will
always work. It should work, I guess about 50% of the time and it is
preferred.

3 How many values of alpha should I try before giving up and going on

Keep alpha, change n.

to the next value of n?

4 When I increase n am I correct to change p so it is > sqrt(nT) or
should I leave it at its original value?

rossum

Depends on how easy it is to find p. I think it's better to shift n,
as that makes it more likely that a solution will work with your
current p anyway.

Looks like the most important variable to change is n: it is your
primary control variable.

Just make sure it isn't even, not divisible by 3, and if you can keep
it from having too many small prime factors, e.g. 5 or 7 are not
preferred versus 107.

Good luck. Based on the current theory, all of that should work
extremely well. If it doesn't, I'll have to dig through and figure
out what I screwed up.


James Harris
.

Relevant Pages

  • Re: JSH: Not obvious? Simple math test.
    ... JSH - January 2008 Factoring method ... RHS of is not a quadratic residue. ... that your choice of alpha will work. ... Questions for James: ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... work either so I suggest it be odd. ... suppose that roughly 50% of the solutions that work for alpha will NOT ... More recalculation means a slower algorithm. ... existence of a quadratic residue modulo p. ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... The instructions were about the variable n. ... suppose that roughly 50% of the solutions that work for alpha will NOT ... existence of a quadratic residue modulo p. ... The original equation did not have a quadratic residue, ...
    (sci.crypt)
  • Re: JSH: Now were golden!
    ... factoring problem, and I want to definitely thank Enrico and would ... which the negative of the quadratic residue is a quadratic residue and ... they are the primes for which the negative of their quadratic residue ... It's a duty. ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... work either so I suggest it be odd. ... suppose that roughly 50% of the solutions that work for alpha will NOT ... More recalculation means a slower algorithm. ... existence of a quadratic residue modulo p. ...
    (sci.crypt)