mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   New Factoring Algorithm (https://www.mersenneforum.org/showthread.php?t=23301)

 GreasyScooby 2018-04-27 02:55

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

 Batalov 2018-04-27 03:14

[QUOTE=GreasyScooby;486322]...so far, mine is exponentially faster. [/QUOTE]
Exponentially? Ok.

You will get many's attention if you factor this little number:
[CODE]
2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271[/CODE]

 CRGreathouse 2018-04-27 03:52

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=GreasyScooby;486322]1. Do you recommend any other factoring algorithms that I can compare to?[/QUOTE]

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=GreasyScooby;486322]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?[/QUOTE]

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.

 axn 2018-04-27 06:29

[QUOTE=GreasyScooby;486322]I have compared my algorithm to msieve and so far, mine is exponentially faster.[/QUOTE]

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.

 Dr Sardonicus 2018-04-27 13:48

[QUOTE=Batalov;486324][QUOTE=GreasyScooby;486322]...so far, mine is exponentially faster.[/QUOTE]Exponentially? Ok.

You will get many's attention if you factor this little number:
[CODE]
2601983048666099770481310081841021384653815561816676201329778087600902014918340074503059860433081046210605403488570251947845891562080866227034976651419330190731032377347305086443295837415395887618239855136922452802923419286887119716740625346109565072933087221327790207134604146257063901166556207972729700461767055550785130256674608872183239507219512717434046725178680177638925792182271[/CODE]