Re: JSH: Not obvious? Simple math test.

On 12 Jan, 00:41, JSH <jst...@xxxxxxxxx> wrote:
On Jan 11, 1:50 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:





On Fri, 11 Jan 2008 06:40:25 -0800 (PST), JSH <jst...@xxxxxxxxx>
wrote:

On Jan 11, 4:56 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Thu, 10 Jan 2008 14:39:07 -0800 (PST), JSH <jst...@xxxxxxxxx>
wrote:

On Jan 10, 2:08 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
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)

[snip]>Greater than 100.  e.g. 107 is a large enough prime.

OK, I will use 100 as the limit.

The instructions were about the variable n.

Its prime factors should be greater than 100, like 107.  But if you
really want to use smaller prime factors you can, as long as n does
not have  3 as a factor--as then the equations just won't work as
proven by me--and I think in a lot of cases with n even they won't
work either so I suggest it be odd.

If, you really want small prime factors for n, they probably won't
make a big difference as I'm talking about an optimal approach, but
they can diminish effectiveness, as, for instance with n=5, you can
suppose that roughly 50% of the solutions that work for alpha will NOT
give you a solution, so with about a 50% probability for the relations
normally, you'd have a total 25% probability from using n=5, or just
having 5 as a factor of n.

though it is important that n not contain a lot of small prime factors.

Would it be an option to limit n to 1, 5, 7, 11, ... - i.e. 1 followed
by the odd primes except 3?  That would give n odd, coprime to 3 and
without a lot of small factors.

5 is a small prime, as is 7.  Keep prime factors of n>100.

But 5 does not "contain a lot of small prime factors", it only
contains one such factor, hardly "a lot".  Are you saying that I
should jump n from 1 to 101?  That would mean frequent recalculation
of p since you just said that for n > 100 I need to recalculate p.
More recalculation means a slower algorithm.

The factorization is of nT, where T is the target composite to be
factored and n is a control variable that is, of course, non-zero and
otherwise your choice, as long as it does not have 3 as a factor, as
if it does the equations won't work.

So I was saying that n should not have 5 as a factor, as that will
diminish the success rate.

[snip]

An alpha for a working quadratic residue is given by

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

where x=y mod p or x = -y mod p

This is of no use here.  I am at step 4 of the algorithm, I have
values for T, p and n.  I do not yet have a value for y (calculated
later in step 6).  Without a value for y this equation is not useful
at this stage of the algorithm.

Hmmm.. that relation is part of the existence proof showing when an
alpha exists.

You deleted so much that I don't remember what was the context for
noting that information.

I was probably justifying some statement.

Alternatively, is there a way to rearrange the algorithm to determine
y before looking at alpha?  In that case this equation would be
useful.

The original equations stand as given:

with z^2 = y^2 + nT

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

where

k^2 = ((a^2)+1)^{-1} (nT) mod p

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

p is some odd prime of your choice, which must be coprime to y, z and
nT, and nT must be coprime to 3, and should be odd.  Then 'a' what I
like to call alpha but the Greek letter doesn't come over very well in
posts so I will also use 'a'--is found such that k exists i.e.
((a^2)+1)^{-1} (nT) is a quadratic residue modulo p.

If p is chosen such that p>sqrt(nT), then you can factor from z-y mod
p or z+y mod p.

I've been explaining to you ways in which you might proceed to figure
out the variables, where I suggested just picking some 'a' and then
changing 'n' so that you get a k, where I've noted that n cannot have
3 as a factor, and should be odd.

Also it helps if n does not have small prime factors like 5 or 7, as
for instance, having 5 as a factor can reduce the success rate by 50%.





so if you go searching with n=1, on a composite with only two prime
factors, I'm worried that your probability of picking the correct
alpha is about 2/(p-2), but I could be wrong.

It's possible the math will simply keep giving the same answers for a
lot of alpha's.

But if it doesn't then it matters that you not search on alpha.  Now
you may think that picking n, doesn't change things much.  Fine.  Just
do it and if you get a crappy method then you can say you followed my
instructions and the ideas just don't work.

I cannot follow your instructions since at this point in the process I
do not have a value for y.  I need an equation for alpha in terms of
T, p and n, which are the only numbers established by this point in
the algorithm.

You choose alpha.  So choosing alpha is the start.  I have given the
equations for determining everything else.

The control variable n is there just to allow you to force the
existence of a quadratic residue modulo p.







But if you search for alpha, you didn't follow my suggestions.

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

Thanks for that.

I spoke too soon, there is an issue here.  The original equation (1)
was:

  z^2 = y^2 + nT

This is not a modular equation, and depending on the values of z, n
and T we could have y complex, real or integer.  Your two substitute
equations are both modular equations which will always have integer
solutions for y - no complex solutions and no real solutions.  I am
doubtful that they will give the same results as the original
equation.

Factoring with the congruences relies on the fact that given z mod p
and y mod p, with p>sqrt(nT) for a non-trivial factorization, you may
factor nT with z-y mod p or z+y mod p.

So there is no calculation of square roots.

Oddly enough, that was the point of the original post in this thread.

Can you please confirm which is the correct way to calculate y at this
stage, the original non-modular equation (1) or the replacement pair
of modular equations.

You should use the equations given which are the congruence relations.

It should make things simpler as now you don't have to resolve a
quadratic residue.

The original equation (1) did not have a quadratic residue, just a
normal square root:

  y = sqrt(z^2 - nT)

No.  If you were following instructions you should not have been
taking a square root, ever.

Hence my doubts about the equivalence of the old and new equations for
determining y.

rossum

The proper technique is to use z-y mod p and z+y mod p, to get the
residue of the factors of nT, as if p>sqrt(nT), then for a non-trivial
factorization where a prime smaller than p is isolated, you will get
that factor as it is its own residue.

Consider, z^2 = y^2 + 119, so n=1, which is the best case.  z=12 and
y=5 will non-trivially factor, but consider them with p=11, as then
you have z = 1 mod 11  and y = 5 mod 11.

And notice then that z-y mod 11 = -4 mod 11 = 7 mod 11, while z+y mod
11 = 6 mod 11.

Notice that the smaller prime factor--7--is given to you directly,
while the larger prime factor--17--is not, though it is close as you
get it by just adding 11.

If you go around taking square roots you will blow up some very simple
mathematical ideas, for no good reason at all, as note what happens if
you try to use z = 1 instead of z=1 mod 11 and take a square root to
solve y.

James Harris- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -

Are you standing by the original estimated date for when you post an
RSA factor? I think we're about 12 days away now, right? I'm just
thinking of selling my 'net stocks you see.
.

Relevant Pages

  • 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.
    ... 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.
    ... 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: Not obvious? Simple math test.
    ... Also nT has to be odd and coprime to 3. ... algorithm then I will need a definite value to compare n with. ... that your choice of alpha will work. ...
    (sci.crypt)
Quantcast