### Tuesday, March 17, 2009

## Factoring problem solution, proof of concept code

Ok, here's a posting of some code which provides the proof of concept for my mathematical proof which solves the factoring problem. The code factors numbers of the form 2^n + 1 because it factors D by factoring D-1, so if D = 2^n + 1, then it's trivial to factor D-1 = 2^n, and also trivial to loop through those factors. Further it is proven that ANY number of that form can be non-trivially factored in at most n+1 iterations! Which I think brings Fermat numbers into reach.

I was going to only post the code to comp.theory as it seems more appropriate but I've been making the case to the physics community that I have actually solved the factoring problem, so I'm including them as well, as with physics people, yeah, a demonstration can be very effective and I'm sure plenty of them can run Java.

The factoring problem IS solved. This code isn't meant to allow you to go factor anything but to demonstrate a very beautiful proof that relies on dual factorizations through Pell's Equation.

James Harris

_____________________________

[A reply to someone who wrote that James' algorithm didn't strike him as faster than trial division.]

You're just repeating other posters who say that over and over again as a "talking point".

The test code says what I've been saying: you CAN factor one number by instead factoring another.

That test code demonstrates factoring D=2^n+1, by looping through factors of 2^n, which is just frakking easy.

Now many of you pretend that you are about knowledge and learning while there are these "crackpots" who are never right, who just annoy you so much, but I say you are nasty, sloppy people who just hate so you spew on other people because you're nasty human beings who like doing nothing better.

For others, what does this result really mean?

Quite simply: you can factor a target composite D, by instead factoring D-1.

RSA encryption relies on having a public key that is supposed to be hard to factor because it is the product of two large primes, so D = p_1*p_2, with big primes.

My approach though allows you to take an alternate approach to factoring D, where rather than go at it head-on, which is what most modern approaches, like say the Number Field Sieve, do, it goes at it at an angle, so now you can factor D, by instead factoring D-1, so you factor p_1*p_2 - 1, and find p_1 and p_2 that way, so your public key can go down by someone factoring some other number.

It is an awesome concept, which I've researched for about 5 years now, and as a basic research concept it produced a hunt like no other, and yes, nasty human beings loved ripping on me about my failures.

But that's not the worst part: it's the fight against success that wraps us and the entire world up into this saga.

Real life isn't so much about high drama and grand things you can see from a mile away. It's not about being able to predict what the next big thing is, or knowing what to do or not to do, but it does punish for inconsistency.

IF the mathematical community were consistent even in its love of "pure math" then a solution using the world famous Pell's Equation, connecting a brilliant idea of finding an alternate approach to factoring would have rang bells, but the math community has NOT been consistent, so now, no one knows what will happen.

But what you can know for certain is: your life will change because of this result.

And that's true no matter who you are, no matter where you are on this planet.

Real life is what happens. It's not a movie, or some book. It's not what you think can happen as reality doesn't give a damn what you think.

If it did, then the world would really be frakking boring, now wouldn't it?

I was going to only post the code to comp.theory as it seems more appropriate but I've been making the case to the physics community that I have actually solved the factoring problem, so I'm including them as well, as with physics people, yeah, a demonstration can be very effective and I'm sure plenty of them can run Java.

The factoring problem IS solved. This code isn't meant to allow you to go factor anything but to demonstrate a very beautiful proof that relies on dual factorizations through Pell's Equation.

James Harris

_____________________________

<code>

import java.lang.Math;

import java.math.BigInteger;

import java.util.ArrayList;

//Code utilizes my surrogate factoring algorithm where the underlying equations rely on

//Pell's Equation and a dual factorization. Go to mymath.blogspot.com for more info.

//To use input a natural number less than 32, like 5, and the code will, for instance, factor 2^5+1

/**

* The FermatNumber class implements an application that

* attempts to factor a number of the form 2^n + 1.

*/

public class FermatNumber {

static int n;

public static void main(String[] args) {

try{

n = Integer.parseInt(args[0]);

if (n>29){

System.out.println("Number too large. Input has to be a positive

integer less than 30.");

System.exit(0);

}

}

catch (NumberFormatException e){

System.out.println("Not a number.");

}

FermatNumber Factorer= new FermatNumber();

Factorer.process();

}

private long D, f_1, h, mult;

private ArrayList<Long> g_2 = new ArrayList<Long>();

private BigInteger BigD;

private double v, max_range, min_range;

private double temp;

private int max_iter;

private int trivial_factors=0;

public FermatNumber(){

}

private void process(){

long temp_long;

//D is of the form 2^n + 1

D = 1<<n;

D++;

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

System.out.println("");

if (checkForSquare(D)){

System.out.println("D is a perfect square.");

System.out.println("sqrt("+D+")="+(long)Math.sqrt(D));

return;

}

BigD = BigInteger.valueOf(D);

f_1 = 1;

mult = 1;

max_iter = n;

for (int i=0; i<max_iter; i++){

f_1 = mult;

//code for the integer v case

h = 1;

for (int j=0; j<i; j++){

temp_long = setIntRad(f_1, h);

if (temp_long>0){

setRange(f_1, temp_long);

searchInt_v(j+1);

}

h = h<<1;

}

//negative case

h = 1;

f_1=-f_1;

for (int j=0; j<i; j++){

temp_long = setIntRad(f_1, h);

if (temp_long>0){

setRange(f_1, temp_long);

searchInt_v(j+1);

}

h = h<<1;

}

//need to make f_1 positive again, may make neater later

f_1 = -f_1;

//Searching for the fractional v case

temp_long = setFracRad(f_1);

if (temp_long<0) break;

setRange(f_1, temp_long);

searchFrac_v();

//now negative values for f_1

f_1 = -f_1;

setRange(f_1, temp_long);

searchFrac_v();

mult = mult<<1;

}

System.out.println("");

System.out.println("");

if (!g_2.isEmpty()){

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

System.out.println("");

Object[] factors = g_2.toArray();

if (trivial_factors>=factors.length) System.out.println(D+" is

prime.");

else{

for (int i=0; i<factors.length; i++){

System.out.println("g_1="+(D/(Long)factors[i])+", "+"g_2="+(Long)

factors[i]);

System.out.println("");

}

}

}

else System.out.println(D+" is prime.");

if (trivial_factors!=0) System.out.println("Trivial factorizations

found: "+trivial_factors);

}

private long r_c(double v_in){

temp = (D+1)*v*v - 2*f_1*v + f_1*f_1;

return (long)(2*temp);

}

private void setRange(long f_in, long other_in){

max_range = (f_in + Math.sqrt(other_in))/(D+1);

min_range = (f_in - Math.sqrt(other_in))/(D+1);

}

private boolean checkGCD(long in_value){

long check_value = BigD.gcd(BigInteger.valueOf(in_value)).longValue

();

if (check_value!=1){

Long add_value = new Long(check_value);

if (!g_2.contains(add_value)){

g_2.add(add_value);

}

if (check_value==D) trivial_factors++;

return true;

}

return false;

}

private boolean checkForSquare(long D){

long temp_long = (long)Math.sqrt(D);

if (temp_long*temp_long == D) return true;

else return false;

}

private long setFracRad(long in_f_1){

return (f_1*f_1 - (f_1*f_1 - D/2)*(D+1));

}

private long setIntRad(long in_f_1, long in_h){

return (f_1*f_1 - (f_1*f_1 - in_h*in_h*D)*(D+1));

}

private void searchFrac_v(){

v = (double)((int)(2*min_range))/2;

if (v<max_range){

do{

checkGCD(r_c(v));

v = v+ 0.5;

}while(v<max_range);

}

}

private void searchInt_v(int in_count){

int c = 1;

for (int k=0; k<in_count; k++){

temp = min_range/c;

if (temp>-1 && temp<1) continue;

v = ((int)temp)*c;

if (v<max_range){

do{

checkGCD(r_c(v));

v = v + c;

}while(v<max_range);

}

c = c<<1;

}

}

}

</code>

[A reply to someone who wrote that James' algorithm didn't strike him as faster than trial division.]

You're just repeating other posters who say that over and over again as a "talking point".

The test code says what I've been saying: you CAN factor one number by instead factoring another.

That test code demonstrates factoring D=2^n+1, by looping through factors of 2^n, which is just frakking easy.

Now many of you pretend that you are about knowledge and learning while there are these "crackpots" who are never right, who just annoy you so much, but I say you are nasty, sloppy people who just hate so you spew on other people because you're nasty human beings who like doing nothing better.

For others, what does this result really mean?

Quite simply: you can factor a target composite D, by instead factoring D-1.

RSA encryption relies on having a public key that is supposed to be hard to factor because it is the product of two large primes, so D = p_1*p_2, with big primes.

My approach though allows you to take an alternate approach to factoring D, where rather than go at it head-on, which is what most modern approaches, like say the Number Field Sieve, do, it goes at it at an angle, so now you can factor D, by instead factoring D-1, so you factor p_1*p_2 - 1, and find p_1 and p_2 that way, so your public key can go down by someone factoring some other number.

It is an awesome concept, which I've researched for about 5 years now, and as a basic research concept it produced a hunt like no other, and yes, nasty human beings loved ripping on me about my failures.

But that's not the worst part: it's the fight against success that wraps us and the entire world up into this saga.

Real life isn't so much about high drama and grand things you can see from a mile away. It's not about being able to predict what the next big thing is, or knowing what to do or not to do, but it does punish for inconsistency.

IF the mathematical community were consistent even in its love of "pure math" then a solution using the world famous Pell's Equation, connecting a brilliant idea of finding an alternate approach to factoring would have rang bells, but the math community has NOT been consistent, so now, no one knows what will happen.

But what you can know for certain is: your life will change because of this result.

And that's true no matter who you are, no matter where you are on this planet.

Real life is what happens. It's not a movie, or some book. It's not what you think can happen as reality doesn't give a damn what you think.

If it did, then the world would really be frakking boring, now wouldn't it?