mersenneforum.org > Math a factorisation algorithm with help of quadratic polynomials
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

Mar 2016

1010000102 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
 factorisation_with_quadratic_polynomials.pdf (31.1 KB, 78 views)

 2021-01-31, 23:24 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5,857 Posts Can you give any examples on decent size numbers?
 2021-02-01, 13:08 #3 Dr Sardonicus     Feb 2017 Nowhere 24·32·31 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
Brady

27·3 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×1,579 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 7 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 3·1,579 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·32·17·31 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

 Thread Tools

 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 18:31.

Fri Apr 16 18:31:34 UTC 2021 up 8 days, 13:12, 0 users, load averages: 1.31, 1.70, 2.15

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.