Re: I was right, surrogate factoring proof

From: Bruce Stephens (bruce+usenet_at_cenderis.demon.co.uk)
Date: 02/14/05 

Date: Sun, 13 Feb 2005 23:22:06 +0000

jstevh@msn.com writes:

[...]

> It does matter. If M is odd, j *has* to be odd.
>
> And I did put in my instructions that information.

You did, you even gave a specific choice of j.

> You didn't follow the algorithm.

True, but it's necessary to factorise T and j, so that puts practical
constraints on j. Presumably it'll be possible to find a way to get
an odd j, but I don't think it's clear that that will help.

Anyway, I tried on two examples, one with M=47*101, j=2373, and that
worked. M=1237*37463, j=23170865 didn't, but j=23170864 did.

So that strongly suggests that the choice of j isn't as arbitrary as
you're making out.

(I didn't carefully choose the counterexample: I just used the first
prime after 1234, and the first prime after a number I got from typing
a few random digits. j is as your algorithm specified.)

[...]

> Well, if you'd followed my instructions, by now you might be emailing
> RSA.
>
> Unless you made some other mistake as well.

You can see the PARI implementation, pari is freely downloadable,
complete with tutorial, user guide, reference card. Why not compare
the implementation with your idea of the algorithm, and see if they
differ? It looks good to me, for what it's worth (I don't know pari,
but I looked up what "fordiv" did, and that made everything clear).

Quantcast