a factorisation algorithm with help of quadratic polynomials

bhelmes · 2021-01-31, 17:06

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.

henryzz · 2021-01-31, 23:24

Can you give any examples on decent size numbers?

Dr Sardonicus · 2021-02-01, 13:08

You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!

jwaltos · 2021-02-01, 15:19

Quote:

Originally Posted by Dr Sardonicus

You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!

I was just doing some online rounds this morning when I came across your post..your response is namesake worthy. In a similar vein, VBCurtis' response, https://www.mersenneforum.org/showth...454#post534454, hit the mark as well (note item 2).
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.

bhelmes · 2021-02-05, 22:04

Quote:

Originally Posted by henryzz

Can you give any examples on decent size numbers?

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

VBCurtis · 2021-02-05, 23:14

"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.

bhelmes · 2021-02-05, 23:58

Quote:

Originally Posted by VBCurtis

"Decent size" is 20+ digits.

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.

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:

Originally Posted by VBCurtis

"
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.

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 p-1 or a p+1 test and I used only an old computer
(AMD FX(tm)-6300 Six-Core Processor)

I think this is not a bad result.

LarsNet · 2021-03-16, 06:21

Where can you look up the numbers, llke M278557, so i can test as well. ( New here, still learning )

VBCurtis · 2021-03-16, 06:30

M is shorthand for Mersenne, so M278557 is 2^278557-1.
The binary representation is quite a bit easier to provide than the decimal!

bhelmes · 2021-03-16, 21:21

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.

Uncwilly · 2021-03-16, 22:00

Quote:

Originally Posted by LarsNet

Where can you look up the numbers, llke M278557, so i can test as well. ( New here, still learning )

If you type the number 278557 into the exponent status page on Mersenne.org, you can find all sorts of info.

2021-02-05, 23:14	#6
VBCurtis "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 2021-02-05 at 23:16

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
special quadratic polynomials : f(n)=an²+bn+1	bhelmes	Number Theory Discussion Group	2	2021-01-24 10:14
primesieves for quadratic polynomials	bhelmes	Math	21	2020-03-19 22:14
euler phi function and quadratic irred. polynomials	bhelmes	Computer Science & Computational Number Theory	2	2019-08-24 15:00
the multiplicativ structur of the discriminant for quadratic polynomials	bhelmes	Computer Science & Computational Number Theory	3	2017-05-27 01:33
Using p=2 for sieving (Quadratic sieve algorithm)	R1zZ1	Factoring	36	2007-11-02 15:59

2021-01-31, 23:24	#2
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5853₁₀ Posts	Can you give any examples on decent size numbers?

2021-02-01, 13:08	#3
Dr Sardonicus Feb 2017 Nowhere 2⁵×139 Posts	You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!

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

2021-03-16, 06:30	#9
VBCurtis "Curtis" Feb 2005 Riverside, CA 1001001111011₂ Posts	M is shorthand for Mersenne, so M278557 is 2^278557-1. The binary representation is quite a bit easier to provide than the decimal!

2021-03-16, 21:21	#10
bhelmes 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.