Re: JSH: Not obvious? Simple math test.

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)

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

I will incorporate the extra limits on n and k.



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.

I do not like negative n, it doubles the size of the search space and
so will double the time the algorithm takes. Is it possible to just
use positive n?

Yes. I was just saying that as an if.

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,

How large is "extremely large"? If I want to put this into a computer
algorithm then I will need a definite value to compare n with.

Greater than 100. e.g. 107 is a large enough prime.

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.

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.

Again I do not like this, it looks like too much work. I have an
algorithm to check if alpha is a quadratic residue and qr's are common
enough that I should only have to try about two values of alpha before
finding one. I do not have an algorithm for telling in advance if any
given n will let my choice of alpha work. It looks to me as if your
suggestion slows the method down, which is that last thing it needs.

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

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.

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.


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


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.

Is this algorithm non-deterministic? Do I use a RNG to select whether
to step alpha, n or p? Is there any problem with just stepping alpha
at this stage? I step n elsewhere, and you were saying above that p
should mostly be left unchanged unless n gets "extremely large".


You can change p at will. You can change n at will as long as it
isn't even, does not have 3 as a factor, and preferably does not have
small primes as a factor, where I've said by "small primes" I mean
primes less than 100.

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.

As I said above, I can check alphas quickly, I do not have a way to
check k's or n's quickly. I know that half of the posible alphas are
qr's, I do not know that half of n's or k's will work. I think that
this will slow down the algorithm.

Then try your way and then try mine.


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.

It is easy to find qr's.





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.

I disagree for reasons I explained above.

It may not matter. Try your way and if it doesn't work, then try mine
before you come back to the newsgroup claiming anything about this
approach.


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.

I will keep p fixed then.



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.

I can do that.

rossum


You may be able to change alpha like you wish, as while I think only 1/
(p-2) of the alphas will work. I may be wrong.

The theory isn't clear to me on the issue. So feel free of course to
try your way.

It's your time.


James Harris
.

Relevant Pages

  • Re: JSH: Not obvious? Simple math test.
    ... by the odd primes except 3? ... More recalculation means a slower algorithm. ... alpha is about 2/, ...
    (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.
    ... 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)