Re: Pell equation X^2=d*Y^2+1 where d=RSA number

On Jan 28, 11:15 pm, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
 Gerry <Gerry...@xxxxxxxxx> wrote:
On Jan 28, 4:18 am, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
 Gerry <Gerry...@xxxxxxxxx> wrote:
On Jan 27, 11:58 pm, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

 Gerry <Gerry...@xxxxxxxxx> wrote:
On Jan 27, 8:47 pm, rich burge <r3...@xxxxxxx> wrote:
On Jan 27, 11:11 am, Gerry <Gerry...@xxxxxxxxx> wrote:

is it possible to find the pell equations of the RSA numbers as
in:

 X^2=d*Y^2+1 where d=RSA number

And could Y in this case have a simple form like for example:

X=3*37239639534523*518144156602508243009*4000659204579114753312310
8788
4704
3­­394855313

d=1238926361552897*93461639715357977769163558199606896584051237541
6381
8858
0­­280321
 Y=2^129

google: lenstra "solving the pell equation"
There is also video available somewhere at MSRI.
Finding solutions for even a moderate size d is not easy.

i believe Lenstra's paper uses continued fractions if i recall it
right.

I believe *everybody* uses continued fractions to solve Pell.

The problem i'm having is not the size of d it is factoring d.
I think i can easily push the size of d into the RSA range.

I don't understand your last sentence. Concerning the size of d,
the continued fraction for sqrt d can be very long, and the smallest
solution of Pell can be very, very, very, very large. I suppose
the smallest Y could have a simple form, but it doesn't seem
the least bit likely.

i believe only solutions for squarefree d values are of interest.

The example i gave was not generated by CF expansion i used my own
identity
which is probably trivial but still interesting.
It generates d values which are composite and also have a factor
like in this case 2 with a high power which can be excluded from d if
square.

I think I understand now - you're not interested in solving
x^2 - d y^2 = 1, given d - you're interested in finding d
for which there is a solution with a nice value of y. So, let y
be your favorite number, let x = y^2 + 1, and then hope
that x + 1 is "an RSA number," by which I take it you mean
a product of two largush primes. Or let x = y^2 - 1 and
hope x - 1 is RSA. If neither one works, go to your second
favorite value of y, and try again. There are enough RSA
numbers around that you probably won't have to work hard.

But what's the point?

there is no real specific point, i only wanted to know if maybe
someone already
found some d=RSA because i think Y should be of a simple form in this
case.

Are you saying that if d is a product of two large primes
then Y will have a simple form? Do you have any reason
for thinking this is the case? Have you chosen 10 or 15
primes, looked at all d = p q where p and q are distinct
primes from your set, and found that in every case Y has
a simple form?

--
Gerry Myerson (ge...@xxxxxxxxxxxxxxx) (i -> u for email)- Hide quoted text -

- Show quoted text -

Hi Gerry,

No d can be a composite of more primes of course.
Here's one with 5 primes and y simple:

x=3*43*283*659*165768537521*762394321774681*359687424377961714750891763743933975334959200103759485840227631801;
y=2^(165);
d=257*12239719573537*18093927039368350337*25394524415842506913*378321539354637595471013489406983903120592833;

Took me under 1 minute to find not using CF.

Regards

Gerry
.

Relevant Pages

  • Re: Weak keys for RSA ?
    ... Robert D. Silverman RSA Public Key Validation, ... that p,q are so-called strong primes. ... outline how to guard against the Bach/Shallit ... a standard. ...
    (sci.crypt)
  • Re: Pell equation X^2=d*Y^2+1 where d=RSA number
    ... Finding solutions for even a moderate size d is not easy. ... I think i can easily push the size of d into the RSA range. ... Are you saying that if d is a product of two large primes ... Gerry Myerson ...
    (sci.math)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.math)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.crypt)
  • Re: Pell equation X^2=d*Y^2+1 where d=RSA number
    ... I think i can easily push the size of d into the RSA range. ... primes from your set, and found that in every case Y has ... interesting that you aren't using continued fractions. ... The notation i'm using always has a common factor for y and d. ...
    (sci.math)