mersenneforum.org > Math a factorisation algorithm with help of quadratic polynomials
 Register FAQ Search Today's Posts Mark Forums Read

2021-01-31, 17:06   #1
bhelmes

Mar 2016

5028 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.
Attached Files

 2021-01-31, 23:24 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 585310 Posts Can you give any examples on decent size numbers?
 2021-02-01, 13:08 #3 Dr Sardonicus     Feb 2017 Nowhere 25×139 Posts You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!
2021-02-01, 15:19   #4
jwaltos

Apr 2012

1011111102 Posts

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.

Last fiddled with by jwaltos on 2021-02-01 at 15:32

2021-02-05, 22:04   #5
bhelmes

Mar 2016

2·7·23 Posts

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

Last fiddled with by bhelmes on 2021-02-05 at 22:06

 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
2021-02-05, 23:58   #7
bhelmes

Mar 2016

2·7·23 Posts

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.

 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 10010011110112 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.
2021-03-16, 22:00   #11
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2×7×677 Posts

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.
Attached Thumbnails

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 2 2021-01-24 10:14 bhelmes Math 21 2020-03-19 22:14 bhelmes Computer Science & Computational Number Theory 2 2019-08-24 15:00 bhelmes Computer Science & Computational Number Theory 3 2017-05-27 01:33 R1zZ1 Factoring 36 2007-11-02 15:59

All times are UTC. The time now is 15:52.

Mon Apr 12 15:52:54 UTC 2021 up 4 days, 10:33, 1 user, load averages: 1.86, 2.00, 2.13