20210131, 17:06  #1 
Mar 2016
502_{8} Posts 
a factorisation algorithm with help of quadratic polynomials
A peaceful and pleasant sunday for you,
I present a new factorisation algorithm, which use quadratic polynomials instead of eliptic curves. It is a preprint and an implementation will follow soon, nevertheless I am interesting for a mathematical feedback. Enjoy the algorithm. 
20210131, 23:24  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5853_{10} Posts 
Can you give any examples on decent size numbers?

20210201, 13:08  #3 
Feb 2017
Nowhere
2^{5}×139 Posts 
You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!

20210201, 15:19  #4  
Apr 2012
Brady
101111110_{2} Posts 
Quote:
For the OP, how difficult was it for you to come up with your idea? Second, look into some of the coding within the forum that may contain mathematical ideas similar to yours..for example, YAFU. Instead of elliptic curves could your method be used? If you can prove something mathematically then your idea may have merit. Can you prove anything about your concept? Just to be fair, I did read your paper and Pauli's quote came to mind. Last fiddled with by jwaltos on 20210201 at 15:32 

20210205, 22:04  #5 
Mar 2016
2·7·23 Posts 
Example : f=14111
M = (A B) (C D) The matrix M is calculated by fast exponention with primes from 2 up to max modulo f basis polynom : 2x²1 (I calculate the primes p  2x²1 with p>x) a) p=17 x=3 M1 = A : 17 B : 3 C : 3 D : 1 M2 = M1² A : 298 B : 54 C : 54 D : 10 ... M2..17 = A : 2366 B : 5754 C : 5754 D : 14011 ERG :137 (=gcd (B, f)) b) p=31 x=4 M1 = A :31 B :4 C :4 D :1 M2 = A : 977 B : 128 C : 128 D : 17 M2..13 = A : 2392 B : 3708 C : 3708 D : 2804 ERG :103 c) p=71 x=6 M1 A : 71 B : 6 C : 6 D : 1 M2 A : 5077 B : 432 C : 432 D : 37 .... M2..17 A : 10713 B : 12257 C : 12257 D : 4121 ERG :103 Is this explication sufficient for understanding the basic algorithm ? Greetings Bernhard Last fiddled with by bhelmes on 20210205 at 22:06 
20210205, 23:14  #6 
"Curtis"
Feb 2005
Riverside, CA
3·19·83 Posts 
"Decent size" is 20+ digits. A toy example that can be solved on pencil and paper (with or without your algorithm) does not demonstrate an algorithm, no.
Using your algorithm to find an 8+ digit factor of a 20+ digit number is a proof of concept, of the sort you wish your provided example was. Using your algorithm to find a 12+ digit factor of a 30+ digit number is at a scale that regular trial division can do in a measurable [fraction of a second?] time. By that size, you may have timing data for your algorithm that can show you how [in]efficient your algorithm is. Last fiddled with by VBCurtis on 20210205 at 23:16 
20210205, 23:58  #7  
Mar 2016
2·7·23 Posts 
Quote:
Mp67 less than a second M1 A :71 B :6 C :6 D :1 M8539 A :108428447244622464955 B :62380898082881687812 C :62380898082881687812 D :69329748362826034141 ERG :761838257287 Quote:
Mp101: 1 sec M1 A :31 B :4 C :4 D :1 M278557 A :51109652505043588650876826875 B :2347607336006370217211437694510 C :2347607336006370217211437694510 D :191163035652478580518938993307 ERG :7432339208719 The program is not optimized for speed, I wanted to demonstrate that this is not a p1 or a p+1 test and I used only an old computer (AMD FX(tm)6300 SixCore Processor) I think this is not a bad result. 

20210316, 06:21  #8 
Mar 2021
2 Posts 
Where can you look up the numbers, llke M278557, so i can test as well. ( New here, still learning )

20210316, 06:30  #9 
"Curtis"
Feb 2005
Riverside, CA
1001001111011_{2} Posts 
M is shorthand for Mersenne, so M278557 is 2^2785571.
The binary representation is quite a bit easier to provide than the decimal! 
20210316, 21:21  #10 
Mar 2016
2·7·23 Posts 
Somebody wanted to know how the sieving for quadratic polynomials is made. I recommand to this topic my (nice) webpage:
http://devalco.de/#106 or my book to this topic: http://devalco.de/quadratic_prime_sieves.pdf For me it was a lot of joy to develop this topic, but perhaps 30 years ago this topic seemed to be more interesting than today. 
20210316, 22:00  #11  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2×7×677 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
special quadratic polynomials : f(n)=an²+bn+1  bhelmes  Number Theory Discussion Group  2  20210124 10:14 
primesieves for quadratic polynomials  bhelmes  Math  21  20200319 22:14 
euler phi function and quadratic irred. polynomials  bhelmes  Computer Science & Computational Number Theory  2  20190824 15:00 
the multiplicativ structur of the discriminant for quadratic polynomials  bhelmes  Computer Science & Computational Number Theory  3  20170527 01:33 
Using p=2 for sieving (Quadratic sieve algorithm)  R1zZ1  Factoring  36  20071102 15:59 