mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-01-31, 17:06   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

5028 Posts
Default 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
File Type: pdf factorisation_with_quadratic_polynomials.pdf (31.1 KB, 77 views)
bhelmes is offline   Reply With Quote
Old 2021-01-31, 23:24   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

585310 Posts
Default

Can you give any examples on decent size numbers?
henryzz is online now   Reply With Quote
Old 2021-02-01, 13:08   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25×139 Posts
Default

You appear to have invented an algorithm which makes trial division seem blindingly fast in comparison. Congratulations!
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-01, 15:19   #4
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Brady

1011111102 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
jwaltos is offline   Reply With Quote
Old 2021-02-05, 22:04   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·7·23 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
bhelmes is offline   Reply With Quote
Old 2021-02-05, 23:14   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·19·83 Posts
Default

"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
VBCurtis is offline   Reply With Quote
Old 2021-02-05, 23:58   #7
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·7·23 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
"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 View Post
"
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.
bhelmes is offline   Reply With Quote
Old 2021-03-16, 06:21   #8
LarsNet
 
Mar 2021

2 Posts
Default

Where can you look up the numbers, llke M278557, so i can test as well. ( New here, still learning )
LarsNet is offline   Reply With Quote
Old 2021-03-16, 06:30   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10010011110112 Posts
Default

M is shorthand for Mersenne, so M278557 is 2^278557-1.
The binary representation is quite a bit easier to provide than the decimal!
VBCurtis is offline   Reply With Quote
Old 2021-03-16, 21:21   #10
bhelmes
 
bhelmes's Avatar
 
Mar 2016

2·7·23 Posts
Default

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.


bhelmes is offline   Reply With Quote
Old 2021-03-16, 22:00   #11
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×7×677 Posts
Default

Quote:
Originally Posted by LarsNet View Post
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
Click image for larger version

Name:	exponent.png
Views:	15
Size:	177.7 KB
ID:	24507  
Uncwilly is offline   Reply With Quote
Reply

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

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

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.