Re: JSH: Not obvious? Simple math test.

On Fri, 11 Jan 2008 06:40:25 -0800 (PST), JSH <jstevh@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.


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.

[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.

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


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.


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.

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.



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)

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

rossum

[snip]

James Harris

.

Relevant Pages

  • Re: Surrogate factoring mysteries resolved
    ... > Now combinations of factors are important, as the proper algorithm ... does the number of divisors increase in a cubic fashion? ... No one doubts that factoring is hard. ...
    (sci.math)
  • Re: Surrogate factoring mysteries resolved
    ... > Now combinations of factors are important, as the proper algorithm ... does the number of divisors increase in a cubic fashion? ... No one doubts that factoring is hard. ...
    (sci.crypt)
  • Re: Bug/Gross InEfficiency in HeathFields fgetline program
    ... But exactly the opposite is true - clarity is lost in *your* version, ... If you think that's a complex algorithm, ... accordance with the Two Rules of Optimisation. ...
    (comp.lang.c)
  • 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: can this code be improved
    ... Why "numberOf" AND "Count"? ... Now we can see what the algorithm is within a few lines of code. ... refactor it further or rewrite it entirely. ...
    (comp.lang.java.programmer)