mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-04-27, 02:55   #1
GreasyScooby
 
Apr 2018

110 Posts
Default New Factoring Algorithm

Hi everyone,

I recently finished a 2-year quest to create a new method of factoring large integers. I have compared my algorithm to msieve and so far, mine is exponentially faster. I have a few questions with regard to this:

1. Do you recommend any other factoring algorithms that I can compare to?

2. I am thinking about releasing it for limited commercial applications. Does anyone know someone I can talk to that can help me with that?

Thank you
GreasyScooby is offline   Reply With Quote
Old 2018-04-27, 03:14   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

Quote:
Originally Posted by GreasyScooby View Post
...so far, mine is exponentially faster.
Exponentially? Ok.

You will get many's attention if you factor this little number:
Code:
2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271
How about it?
Batalov is offline   Reply With Quote
Old 2018-04-27, 03:52   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

First of all, welcome to the forum.

Congrats on your discovery. It's generally hard to convince mathematicians that you've made a breakthrough in a well-researched area, but fortunately factorization is special -- all you have to do is post factorizations of numbers known or widely believed to be hard and you'll have people beating the proverbial path to your door.

Quote:
Originally Posted by GreasyScooby View Post
1. Do you recommend any other factoring algorithms that I can compare to?
The state-of-the-art algorithm for factoring large numbers (after preprocessing to remove small factors) is the number field sieve. I'm not sure what the best implementation is but something like msieve for GPU poly select, GGNFS for sieving, and maybe msieve for the linear algebra. Most of the time is spent in GGNFS, potentially across many client machines.

Quote:
Originally Posted by GreasyScooby View Post
2. I am thinking about releasing it for limited commercial applications. Does anyone know someone I can talk to that can help me with that?
I'm available for consulting, PM me if interested. Fair warning: the market for factorization programs goes from worthless to "so valuable you need bodyguards" very quickly.
CRGreathouse is offline   Reply With Quote
Old 2018-04-27, 06:29   #4
axn
 
axn's Avatar
 
Jun 2003

4,789 Posts
Default

Quote:
Originally Posted by GreasyScooby View Post
I have compared my algorithm to msieve and so far, mine is exponentially faster.
Do you have data to back up that assertion? What size composites have you factored? How much time did it take for your algo vs msieve? Please post some hard figures.
axn is offline   Reply With Quote
Old 2018-04-27, 13:48   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×35 Posts
Default

Quote:
Originally Posted by Batalov View Post
Quote:
Originally Posted by GreasyScooby View Post
...so far, mine is exponentially faster.
Exponentially? Ok.

You will get many's attention if you factor this little number:
Code:
2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271
How about it?
For GreasyScooby's ease of reference, post the factorization to "I want to factorize 2^1277-1" thread in Information & Answers.

Last fiddled with by Dr Sardonicus on 2018-04-27 at 13:51 Reason: Inserting reference to OP
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Alternatively-gifted factoring algorithm Prime95 Miscellaneous Math 72 2015-10-26 00:14
Shor's Factoring Algorithm - does it even work? Citrix Factoring 37 2008-08-16 14:19
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
Faster Factoring Algorithm? Citrix Factoring 6 2007-12-23 11:36
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 21:00.

Thu Dec 3 21:00:47 UTC 2020 up 17:12, 1 user, load averages: 2.41, 2.22, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.