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/

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.
[.snip]
I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.

RSA-160 is factored!
RSA-155 is factored!
RSA-140 is factored!

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.

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'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.

James Harris wrote:

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.


At least you won't be spamming USENET news from jail!

In article <3c65f87.0311260644.75a011d6@posting.google.com> jstevh@msn.com (James Harris) writes:
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.

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/

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.

Are we playing "Smother James with Prime Counting Methods Until he
SCREEMS"? Can I join?

First a slight modification of Abigail's Perl one-liner
to make it a prime counter, rather than a prime lister:

perl -le 'print~~grep!/^(xx+)\1+$/,map x x$_,2..pop' [number]

And now my Magnum Opus! Let

W(2) = 1
W(k) = ((k-1)^2 * W(k-1) + 2)/k - 1 for k > 2

Then

pi(n) = Sum for k = 2 to n: 1 - ceil(W(k) - floor(W(k)))

Same thing in Maple code:

W := k -> ((k-1)^2 * W(k-1) + 2)/k - 1:
W(2) := 1:
pi := n -> sum('1 - ceil(W(k) - floor(W(k)))', 'k'=2..n):

Lo and behold! pi(100) gives 25!

So, where can I collect my trillions of dollars? And the babes! Let's not
forget the babes! Where can I get some of those?

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.

"James Harris" <jstevh@msn.com> wrote in message
news:3c65f87.0311260644.75a011d6@posting.google.com...
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.
[.snip]
I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.


Ah Mr. Harris, name calling once again, so colorful during the holidays!
Are you a real-life scrooge?

If you want fame and fortune, then break the RSA factoring challenge and you
will get both.

You can find it at: http://www.rsasecurity.com/rsalabs/challenges/factoring/
[snip]

A cash prize is awarded to the first person to factor each challenge number.
The prize amount is listed on the page with the challenge number. Prizes
range from $10,000 (US) for the 576-bit challenge to $200,000 for 2048 bits.
The prize money will be paid once RSA Laboratories has verified the
correctness of the factorization.

Here is the set of numbers:

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

Simple problems to state: find the distinct prime factors of each challenge
number.

See if can be beat us instead of name-calling and generalizing all of us you
NPD afflicted ignoramus!

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.

I'm including my search program. It's set up for 119, but an RSA
number is commented out, so it's included. I've looked at cubics, but
you can use any positive integer root, so maybe there's something at 7
or 13, as oh yeah, you need to take odd roots.

I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.

James Harris

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.

I'm including my search program. It's set up for 119, but an RSA
number is commented out, so it's included. I've looked at cubics, but
you can use any positive integer root, so maybe there's something at 7
or 13, as oh yeah, you need to take odd roots.

I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.


James Harris

--------------------------------------

import java.math.*;

public class nFactor {

/** Creates a new instance of Class */
public nFactor() {
}



//5730672984869888900274730318781719609808548531129165133742
//5730672984869888900274730318781719609808548531129165133742
//4540136492434944450137365159390859804904274265564582566870


//15337813277998919321645543772253417309098573760903952911091846426480655749

//
8855290624832892420800470613163063536742910856190682369283097619983989142110

static BigInteger prevr, r, BigK;

static private int count, next, next2;

static public void main(String args[]){

r = new BigInteger("100000000000000");

BigInteger RSA=new
BigInteger("119");//"1881988129206079638386972394616504398071635633794173827

BigInteger base, remainder, mRSA, nRSA;

BigInteger hold, compare, check, mult=BigInteger.ONE;

int t=3;

for (int k=1; k<100; k++){

nRSA = RSA.multiply(mult);

base = rootCalc(nRSA, t).add(BigInteger.ONE);

mult = mult.add(BigInteger.ONE);

remainder = (base.pow(t)).subtract(nRSA);

for (int j=mult.intValue()+1; j<200; j++){

mRSA = RSA.multiply(BigInteger.valueOf(j));

hold = rootCalc(mRSA,t).add(BigInteger.ONE);

compare = (hold.pow(t)).subtract(mRSA);

check = compare.mod(remainder);

if (check.compareTo(BigInteger.ZERO)==0){

System.out.println("found it");

System.out.println("hold="+hold);
System.out.println("base="+base);

System.out.println("remainder="+remainder);
System.out.println("compare="+compare);

BigInteger result=compare.divide(remainder);
System.out.println("compare/remainder="+result);

System.out.println("j="+j);
System.out.println("k="+k);

System.out.println("");

}
}
}


System.out.println("done");


//System.out.println(RSA);


}

private static boolean isEven(int x){

if (x%2==0) return true;
else return false;
}

private static BigInteger SqCalc(BigInteger z){

for (int count=0; count<512; count++){

prevr = ((z.divide(r)).add(r)).shiftRight(1);

if (prevr.compareTo(r)==0){

return r;
}

r=prevr;

}

System.out.println("Exceeded count square root may be
invalid.");
System.out.println("z="+z);
System.out.println("r="+r);

return r;

}

private static BigInteger rootCalc(BigInteger z, int k){


BigK = BigInteger.valueOf(k);

for (int iter=0; iter<1024; iter++){

prevr =
r.subtract(((r.pow(k)).subtract(z)).divide((r.pow(k-1)).multiply(BigK)));


if (prevr.compareTo(r)==0){

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

return r;
}

r=prevr;

}

System.out.println("Exceeded count root calc may be
invalid.");
System.out.println("z="+z);

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

System.out.println("r="+r);

return r;

}



}

[...]

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

I'm including my search program. It's set up for 119, but an RSA
number is commented out, so it's included. I've looked at cubics, but
you can use any positive integer root, so maybe there's something at 7
or 13, as oh yeah, you need to take odd roots.

I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.

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.

I'm including my search program. It's set up for 119, but an RSA
number is commented out, so it's included. I've looked at cubics, but
you can use any positive integer root, so maybe there's something at 7
or 13, as oh yeah, you need to take odd roots.

I'll get back to trying to crack RSA. It amazed me that because
mathematicians are such assholes that I have to try and break down
Internet security to get anywhere. Oh well, it's not my fault.


James Harris

--------------------------------------

import java.math.*;

public class nFactor {

/** Creates a new instance of Class */
public nFactor() {
}



//5730672984869888900274730318781719609808548531129165133742
//5730672984869888900274730318781719609808548531129165133742
//4540136492434944450137365159390859804904274265564582566870


//15337813277998919321645543772253417309098573760903952911091846426480655749

//
8855290624832892420800470613163063536742910856190682369283097619983989142110

static BigInteger prevr, r, BigK;

static private int count, next, next2;

static public void main(String args[]){

r = new BigInteger("100000000000000");

BigInteger RSA=new
BigInteger("119");//"1881988129206079638386972394616504398071635633794173827

BigInteger base, remainder, mRSA, nRSA;

BigInteger hold, compare, check, mult=BigInteger.ONE;

int t=3;

for (int k=1; k<100; k++){

nRSA = RSA.multiply(mult);

base = rootCalc(nRSA, t).add(BigInteger.ONE);

mult = mult.add(BigInteger.ONE);

remainder = (base.pow(t)).subtract(nRSA);

for (int j=mult.intValue()+1; j<200; j++){

mRSA = RSA.multiply(BigInteger.valueOf(j));

hold = rootCalc(mRSA,t).add(BigInteger.ONE);

compare = (hold.pow(t)).subtract(mRSA);

check = compare.mod(remainder);

if (check.compareTo(BigInteger.ZERO)==0){

System.out.println("found it");

System.out.println("hold="+hold);
System.out.println("base="+base);

System.out.println("remainder="+remainder);
System.out.println("compare="+compare);

BigInteger result=compare.divide(remainder);
System.out.println("compare/remainder="+result);

System.out.println("j="+j);
System.out.println("k="+k);

System.out.println("");

}
}
}


System.out.println("done");


//System.out.println(RSA);


}

private static boolean isEven(int x){

if (x%2==0) return true;
else return false;
}

private static BigInteger SqCalc(BigInteger z){

for (int count=0; count<512; count++){

prevr = ((z.divide(r)).add(r)).shiftRight(1);

if (prevr.compareTo(r)==0){

return r;
}

r=prevr;

}

System.out.println("Exceeded count square root may be
invalid.");
System.out.println("z="+z);
System.out.println("r="+r);

return r;

}

private static BigInteger rootCalc(BigInteger z, int k){


BigK = BigInteger.valueOf(k);

for (int iter=0; iter<1024; iter++){

prevr =
r.subtract(((r.pow(k)).subtract(z)).divide((r.pow(k-1)).multiply(BigK)));


if (prevr.compareTo(r)==0){

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

return r;
}

r=prevr;

}

System.out.println("Exceeded count root calc may be
invalid.");
System.out.println("z="+z);

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

r =
(((BigK.subtract(BigInteger.ONE)).multiply(r.pow(k)).add(z)).divide((r.pow(k

System.out.println("r="+r);

return r;

}



}

On Wed, 26 Nov 2003 15:21:41 GMT, "Dik T. Winter" <Dik.Winter@cwi.nl
in sci.cognitive 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.

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.