Re: A89: Linux Port for 89/92

[Prev][Next][Index][Thread]

Re: A89: Linux Port for 89/92


Well, if you know n, then finding p and q is easy, as they are the only
factors of n.  I know this because it is stated on the RSA site that both p
and q are prime numbers, and a prime multiplied with another prime will give
you a number that has only those two primes as factors.

It wouldn't be a major waste of time if I found more than 3 factors (meaning
that there was a typo) or if one of the factors was less than 2^128 as you
say.

Factoring this way might be slow, yes, but I do not have the math knowledge
to use such algorithms that the RSA site suggests.  I do not know a single
person who has spoken about doing anything near eliptic curves and such that
are required for those high-level algorithms.

Math comes very easy to me, but I do not consider myself a 'math wiz'
either...

-Miles Raymond      EML: m_rayman@bigfoot.com
ICQ: 13217756       IRC: Killer2        AIM: KilIer2 (kilier2)
http://www.bigfoot.com/~m_rayman/

----- Original Message -----
From: Johan <johei804@student.liu.se>
To: <assembly-89@lists.ticalc.org>
Sent: Thursday, July 15, 1999 3:47 PM
Subject: Re: A89: Linux Port for 89/92


> On Thu, Jul 15, 1999 at 14:46:41 -0500, Miles Raymond wrote:
> >
> > Why does n have a lower limit of 2^504??
>
> The numbers are always 64 bytes long, and the lowest number that needs 64
> bytes is 2^504, the largest number is 2^512-1.
>
> n (on the TI89) is ...
> 7,199,583,456,868,477,363,672,043,865,116,047,229,712,788,448,020,653,
> 515,684,330,784,137,805,088,971,433,273,011,970,552,138,960,583,799,
> 368,215,373,582,308,591,928,985,045,059,261,105,298,431,035,818,727.
>
> (I'm not 100% sure, because I haven't studied the number format in detail
> yet, and I might have made a typo somewhere. So don't waste your time on
> factoring this number, ok? :)  It's presented here so you can get a
feeling
> of the problem we're facing...)
>
> > Yes, I know how long it can take to factor, since I tried
factor(2^512-1) on
> > my TI-89 with no result for about an hour... But I think there can be a
> > quicker way to get the results we want, not neccessarily to factor it...
>
> According to my TI89 Guide Book, factoring a 100-digit number can take
more
> than a century on the calc... nice try ;)
>
> > (and if it does, in fact, have a lower limit of 2^504, that makes it
> > easier!)
>
> The numbers less than 2^504 is 0.4% of all numbers less than 2^512... it's
> not a "big" win...
>
> > A factoring program works something like divide by 2 till not possible
> > (with integer result), then 3 till not possible, then 5, then the next
> > prime, and so on... right?
>
> No, that's the slowest way to factor a number. There are many faster
> algorithms. (See the RSA Labs FAQ.)
>
> > But because these are special circumstances, we
> > don't have to check for 2 (because we skip all of the evens) and if our
> > number _is_ divisible by a low prime, then we can skip it, assuming that
> > niether p nor q is a small prime.  Where you draw the line is your
choice.
>
> I don't *know* anything about p and q, except that their product is n, but
I
> assume that they're somewhere between 2^128..2^384.
>
> > Or, if you don't like that, (I thought of another way while typing that)
you
> > can skip the number when you find 3 factors, or have a little of both.
This
> > will decrease the time necessary to find out list of possible n's...
>
> I still don't think that getting a list of all n's is the way to go...
this
> list would be H-U-G-E.
>
> The problem is that we want the "e" value, and factoring n to get p and q
> seems to be a good place to start, but I'm not a math wiz and someone else
> might come up with a better idea... We'll need *lots* of computer power to
> break this in reasonable time.
>
> file://Johan
Follow-Ups: References: