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

On Feb 1, 1:05 am, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
 Gerry <Gerry...@xxxxxxxxx> wrote:
On Jan 31, 11:22 pm, Gerry <Gerry...@xxxxxxxxx> wrote:
On Jan 31, 11:08 pm, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

 Gerry <Gerry...@xxxxxxxxx> wrote:
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*400065920457911
475331
2310
8788
4704
3­­394855313

d=1238926361552897*9346163971535797776916355819960689658
405123
7541
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?

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*3596874243779617147508917637
439­­339
75334959200103759485840227631801;
y=2^(165);
d=257*12239719573537*18093927039368350337*25394524415842506913*378321539
354­­637
595471013489406983903120592833;

Took me under 1 minute to find not using CF.

Continued fractions are a way of finding x & y if someone
hands you d. Since that's not what you're doing, it's not
interesting that you aren't using continued fractions.

I've already explained that there's no difficulty finding solutions
to x^2 - d y^2 = 1 if you start with y and then look for d and x.

do you know if there are certain notations for d which always give a
solution?

I mean of course wihout CF and which would be primitive.

I don't know what you mean by "notations for d."
For all d, there are solutions to x^2 - d y^2 = 1,
regardless of notation.
Those solutions can, in general, be found most efficiently
using continued fractions, but of course you could just try
y = 1, y = 2, y = 3, ... until you get to a solution; that's one
way to find a solution without using continued fractions.

Perhaps you are asking are there families of values of d
for which there are simple formulas for x and y.
There are some small values of |k| for which there are
simple formulas for x and y when d = n^2 + k for some n.
These values of k are very small, and very few - they are
all divisors of 4. Details can be found in lots of intro
number theory texts.

There may be some other such families of values of d.

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

- Show quoted text -

Hi Gerry,

Okay the simple formulas i guess something like d=p^2+2 p=prime.

The notation i'm using always has a common factor for y and d.

Give me any positive number and i can give a solution where y and d
have this factor.
No matter which size.

Regards

Gerry
.

Relevant Pages

  • 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. ... here's another example of my notation: ...
    (sci.math)
  • 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. ... primes from your set, and found that in every case Y has ... Continued fractions are a way of finding x & y if someone ...
    (sci.math)
  • 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
    ... I think i can easily push the size of d into the RSA range. ... interesting that you aren't using continued fractions. ... I don't know what you mean by "notations for d." ... 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)
Quantcast