A fellow with an idiot-savant miracle calculator friend could really
clean up! Let's see if Harris, an idiot, can demonstrate the gained
efficacy of downsizing. One need only have a table of primes smaller
than the square root of each RSA number,

In article <3fc4d84f.78540739@netnews.att.net> lesterDELzick@worldnet.att.net (Lester Zick) writes:
On Wed, 26 Nov 2003 15:21:41 GMT, "Dik T. Winter" <Dik.Winter@cwi.nl
in sci.cognitive wrote:
...
[ Snipped James method where he uses differences of two cubes.]

This comes pretty close to the method Fermat used. (Find two squares whose
difference is 0 mod the number to be factored.) I would think working with
squares is faster.

This turns out to be incorrect in my own rather limited amateur
experience. I have programmed a number of algorithms along this line
and have produced none as fast as serial division by successive odd
numbers.

Works well indeed with small numbers (say 20/25 digits or less) or when
there is a relatively very small divisor. Most modern methods try to
find two squares with a difference that is 0 mod the number to be
factored, it is only the way those numbers are found that varies quite
a bit.

Going from Fermat through Quadradic Sieve through Multiple
Polynomial Quadratic Sieve, to the same with large primes, and next to
the Number Field Sieve. The only feasable other method currently in
use is the Elliptic Curves method, which works best if there is a large
prime factor. So it does not go well with the RSA challenges, as they
have two prime factors in the neighbourhood of the square root of the
number.

But my remark more meant that working with squares would be faster than
working with cubes (as James proposed).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

In message <3FC4E38F.B6ED25D8@hate.spam.net>, Uncle Al
UncleAl0@hate.spam.net> writes
A fellow with an idiot-savant miracle calculator friend could really
clean up! Let's see if Harris, an idiot, can demonstrate the gained
efficacy of downsizing. One need only have a table of primes smaller
than the square root of each RSA number,

Have you counted them? I believe Harris has an algorithm that will do
that, too

On Thu, 27 Nov 2003 12:56:42 GMT, "Dik T. Winter" <Dik.Winter@cwi.nl
in sci.cognitive wrote:
....
Works well indeed with small numbers (say 20/25 digits or less) or when
there is a relatively very small divisor. Most modern methods try to
find two squares with a difference that is 0 mod the number to be
factored, it is only the way those numbers are found that varies quite
a bit.

This is probably where I'm going wrong. Difference between serious and
amateur math I suspect.

On Wed, 26 Nov 2003 15:21:41 GMT, Dik T. Winter wrote:

This comes pretty close to the method Fermat used. (Find two squares whose
difference is 0 mod the number to be factored.) I would think working with
squares is faster. But Fermat's method has been improved considerably to
the multiple quadratic sieve method, which works reasonably well for numbers
up to (say) 150 digits. The current method is the number field sieve, which
is similar to the quadratic sieve method, but works in different number
fields. It would do you good to delve into the methods currently used
before you go the long path from Fermat's method to the current methods.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik, you're too kind, offering help like that. James will take it as
criticism - IOW, he will claim you are an asshole for not recognising that
he's a genius to have thought of this method without reading up on it first.

Besides, since it's "close" to Fermat's method, but not the same, it's
obviously original, and James will expect accolades and tons of money for
finding it. Even if it's no improvement on existing methods.

Heh heh

Don't be silly. I don't have to argue about factoring as if I break
RSA encryption, believe me, I won't have to work to convince anyone.

I'm in a desperate situation. I have "pure math" results which should
get me accolades but instead I'm called names and mostly ignored.
Before I've tried to break RSA encryption--the basis for Internet
security--and failed miserably, but it looks like I still have no
choice but a practical math result.

So I'm back at it. If I break RSA then there won't be any debates
about the value of my work, or its correctness.

I came across a new idea that I'd like to mention that might be
fruitful.

Consider 119=7(17), and of course I use small numbers to search for
new ideas, as they're easier to work with than the monster numbers
that are the ultimate targets.

Now it can be shown by finding the first cube above 119, which is 125
that

5 = 6^{1/3} mod 17, or mod 7

but a quick search reveals that

8 = 36^{1/3} mod 17, or mod 7

so

8 = 25 mod 17

which gives the factor. The problem is, it looks a lot like chance,
and some quick tries with bigger numbers didn't get me much. But I've
expanded the way I search and it looks more promising.

It's probably a crap idea, but as usual, I'll toss it out on the
Internet.

jstevh@msn.com (James Harris) wrote in message
news:<3c65f87.0311260644.75a011d6@posting.google.com>...
I'm in a desperate situation.

It might take a few years to figure it all out.

Here's an embarrassing fact:

I took a look at the shortest RSA challenge, and thought, "that doesn't look
TOO big". In high school I wrote a c program that could calculate all the
primes less than 1 billion in about 30 seconds. So let's do a little math.

As an idiot, the best method I personally know how to code is a sort of
seive. So to factor the RSA challenge problem, it would take my computer
(not adjusted for the fact that my simple program would quickly choke since
it uses long int) about:
(the square root of the smallest RSA problem number is about 1.4 * 10^87)

(30 sec / 1 billion) * (1 / 1.4*10^87) * (min / 60 sec) * (hour / 60 min) *
(day / 24 hour) * (year / 365 days)

or about: 1.33 * 10^72 YEARS

think how much the money will be worth when I finally finish! with all the
interest (5%/year) , it will be:
(accourding to maple) 10000*1.05^(1.33*10^72);

Float(infinity)

Easily making me the richest person in the usualverse.

Justin Van Winkle