amorosi - new fast factorization not deterministic

Alberico Lepore · 2018-01-18, 11:47

https://github.com/Piunosei/Amorosi
theory at
https://github.com/Piunosei/Amorosi/wiki

what do you think?

CRGreathouse · 2018-01-18, 16:11

I ran it on the first 1000 composite numbers (4 to 1197). It factored 448 of them in 64 seconds and reported no factors for the remaining 552. (For comparison, you'd factor 597 using trial division up to 2.) Up to 100 the numbers it couldn't factor:

4, 6, 8, 9, 12, 14, 16, 18, 21, 22, 24, 27, 28, 32, 33, 36, 38, 42, 44, 46, 48, 49, 54, 56, 57, 58, 62, 63, 64, 66, 69, 72, 76, 77, 81, 84, 86, 87, 88, 92, 93, 94, 96, 98, 99

CRGreathouse · 2018-01-18, 17:18

I also ran it on a random sample of 10-digit hard semiprimes (pq with q/2 < p <= q) and it was not able to factor any of them.

Batalov · 2018-01-19, 00:58

There was a cult novel in the USSR, by a pair of the talented satirists from the 1930s, Ilf and Petrov.
It is extremely highly quotable.

So in one of the chapters, they describe a character -- "Mechanic Polesov was very inventive. Constantly invented something new. He even invented his own internal combustion engine, very much like a real one, with only one difference - it wouldn't run."

There is another, a shorter but somewhat coarse Russian joke about inventions like these:
The famous Soviet-made butt whistle. Doesn't whistle... and doesn't fit in the butt.

ewmayer · 2018-01-19, 01:06

Serge's mention of the legendary Arschpfeife brought to mind a classic limerick:

There once was a man from Madras,
Whose balls were made of pure brass.
When jangled together,
They played "stormy weather",
And lightning shot out of his ass.

Alberico Lepore · 2018-01-19, 11:38

I have updated

https://github.com/Piunosei/Amorosi
theory at
https://github.com/Piunosei/Amorosi/wiki

what do you think?

2018-01-18, 11:47	#1
Alberico Lepore May 2017 ITALY 20A₁₆ Posts	amorosi - new fast factorization not deterministic https://github.com/Piunosei/Amorosi theory at https://github.com/Piunosei/Amorosi/wiki what do you think?

2018-01-19, 01:06	#5
ewmayer ∂²ω=0 Sep 2002 República de California 3²·1,303 Posts	Serge's mention of the legendary Arschpfeife brought to mind a classic limerick: There once was a man from Madras, Whose balls were made of pure brass. When jangled together, They played "stormy weather", And lightning shot out of his ass. Last fiddled with by ewmayer on 2018-01-19 at 01:07

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semiprimes factoring. Is deterministic? What is computational complexity?	Alberico Lepore	Alberico Lepore	43	2017-06-10 15:42
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!)	jasong	jasong	35	2016-12-11 00:57
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?	Raman	Factoring	1	2016-05-23 13:44
a new Deterministic primality testing	wsc812	Computer Science & Computational Number Theory	36	2013-03-04 06:25
Fast factorization method or crankery?	10metreh	Factoring	6	2010-04-08 11:51

2018-01-18, 16:11	#2
CRGreathouse Aug 2006 175B₁₆ Posts	I ran it on the first 1000 composite numbers (4 to 1197). It factored 448 of them in 64 seconds and reported no factors for the remaining 552. (For comparison, you'd factor 597 using trial division up to 2.) Up to 100 the numbers it couldn't factor: 4, 6, 8, 9, 12, 14, 16, 18, 21, 22, 24, 27, 28, 32, 33, 36, 38, 42, 44, 46, 48, 49, 54, 56, 57, 58, 62, 63, 64, 66, 69, 72, 76, 77, 81, 84, 86, 87, 88, 92, 93, 94, 96, 98, 99

2018-01-18, 17:18	#3
CRGreathouse Aug 2006 3·1,993 Posts	I also ran it on a random sample of 10-digit hard semiprimes (pq with q/2 < p <= q) and it was not able to factor any of them.

2018-01-19, 00:58	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11×19×47 Posts	There was a cult novel in the USSR, by a pair of the talented satirists from the 1930s, Ilf and Petrov. It is extremely highly quotable. So in one of the chapters, they describe a character -- "Mechanic Polesov was very inventive. Constantly invented something new. He even invented his own internal combustion engine, very much like a real one, with only one difference - it wouldn't run." There is another, a shorter but somewhat coarse Russian joke about inventions like these: The famous Soviet-made butt whistle. Doesn't whistle... and doesn't fit in the butt.

2018-01-19, 11:38	#6
Alberico Lepore May 2017 ITALY 2×3²×29 Posts	I have updated https://github.com/Piunosei/Amorosi theory at https://github.com/Piunosei/Amorosi/wiki what do you think?