mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-12-11, 13:47   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default An Analytic Approach to Subexponential Factoring

Francesco Sica
De Factorisatione Numerorum I : An Analytic Approach to Subexponential Factoring

http://arxiv.org/abs/0912.1585

Alex

Last fiddled with by akruppa on 2009-12-11 at 13:48
akruppa is offline   Reply With Quote
Old 2009-12-11, 17:17   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by akruppa View Post
Francesco Sica
De Factorisatione Numerorum I : An Analytic Approach to Subexponential Factoring

http://arxiv.org/abs/0912.1585

Alex
If this thing is real, it is a significant advance, because it
gets rid of the (log log N)^(1-alpha) term in the exponent
for the time complexity of existing algorithms.

e.g. NFS runs in time exp( (1+o(1))( (log N)^1/3 (loglog N)^2/3))

this advance would get rid of the (loglog N)^2/3. ---> A big theoretical
speed improvement.

If it works. If it is practical.
R.D. Silverman is offline   Reply With Quote
Old 2009-12-11, 18:05   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
If this thing is real, it is a significant advance, because it
gets rid of the (log log N)^(1-alpha) term in the exponent
for the time complexity of existing algorithms.

e.g. NFS runs in time exp( (1+o(1))( (log N)^1/3 (loglog N)^2/3))

this advance would get rid of the (loglog N)^2/3. ---> A big theoretical
speed improvement.

If it works. If it is practical.
I will read the paper over the weekend. It is a genuine effort.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best approach for P-1? Mark Rose PrimeNet 6 2017-05-23 23:58
Unorthodox approach to primes Erkan PrimeNet 7 2017-01-10 03:34
a backwards approach to Mersenne testing Mini-Geek Information & Answers 14 2010-11-14 16:16
Best approach for 130 digits? boothby Factoring 10 2009-10-16 17:24
Factoring with the birthday problem approach ThiloHarich Factoring 0 2009-08-18 16:48

All times are UTC. The time now is 01:56.

Tue May 11 01:56:48 UTC 2021 up 32 days, 20:37, 1 user, load averages: 3.31, 3.20, 3.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.