Re: JSH: Not obvious? Simple math test.
- From: rossum <rossum48@xxxxxxxxxxxx>
- Date: Fri, 11 Jan 2008 12:56:22 +0000
On Thu, 10 Jan 2008 14:39:07 -0800 (PST), JSH <jstevh@xxxxxxxxx>
wrote:
On Jan 10, 2:08 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:I will incorporate the extra limits on n and k.
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 do not like negative n, it doubles the size of the search space and
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.
so will double the time the algorithm takes. Is it possible to just
use positive n?
How large is "extremely large"? If I want to put this into a computer
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,
algorithm then I will need a definite value to compare n with.
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.
Again I do not like this, it looks like too much work. I have an4 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.
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.
Thanks for that.
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
Is this algorithm non-deterministic? Do I use a RNG to select whether
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.
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".
As I said above, I can check alphas quickly, I do not have a way to8 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.
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.
It is easy to find qr's.
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.
I disagree for reasons I explained above.
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 will keep p fixed then.
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 can do that.
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.
rossum
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
.
- Follow-Ups:
- Re: JSH: Not obvious? Simple math test.
- From: JSH
- Re: JSH: Not obvious? Simple math test.
- References:
- JSH: Not obvious? Simple math test.
- From: JSH
- Re: JSH: Not obvious? Simple math test.
- From: rossum
- Re: JSH: Not obvious? Simple math test.
- From: JSH
- JSH: Not obvious? Simple math test.
- Prev by Date: Re: MLB - Does Anyone Really Care Anymore?
- Next by Date: SCI .CRYPT
- Previous by thread: Re: JSH: Not obvious? Simple math test.
- Next by thread: Re: JSH: Not obvious? Simple math test.
- Index(es):
Relevant Pages
|
