mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2017-12-12, 20:44   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2×32×29 Posts
Default Factorization and primality test O([log_9(N)]^3)

Factorization and primality test O([log_9(N)]^3)

https://www.academia.edu/35412746/Te...n_O_log_9_N_3_

What do you think of this?
Alberico Lepore is offline   Reply With Quote
Old 2017-12-12, 21:38   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
Factorization and primality test O([log_9(N)]^3)

https://www.academia.edu/35412746/Te...n_O_log_9_N_3_

What do you think of this?
proof of concept without the download and translation ...
science_man_88 is offline   Reply With Quote
Old 2017-12-12, 21:49   #3
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

tomorrow night.
now in Italy it's late.
try to understand
Alberico Lepore is offline   Reply With Quote
Old 2017-12-13, 06:25   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

I don't read Italian. I looked at the document through Google Translate and I couldn't make heads or tails of it. Trying to work through the example I get H = 259 which doesn't give an integral K. But even if we were supposed to follow the cleanup procedure at the bottom of the second page, I don't see how any of this yields information on the factorization of the number.

But I think I should give you and your method a chance. Would you use it to factor some of these numbers, as far as it can reasonably go? Since it takes only cubic time, it should take only ~ k/3.7 seconds for a 1 GHz computer to factor the largest of these, for some constant k which you haven't revealed.
Code:
64 bits: 12948110090585311979

128 bits: 191875610236165000493961741999993232961

256 bits: 104346515658715073236701578230537664345079731008268447250755923399969554554527

512 bits: 8877405418354614101337795613309676609673488389927337368943966383733022288825857519728174752110656132115481773164541042027077109668409285166080822943514087

1024 bits: 110017842535385107563795555661123030649928671048545795736220084126740077360535371108397605185633055628612036218921956452272449040580855582723250597770349258450200896920600054607239415068082852975938869913095282502118922681797947602970968857144251026353070249934660110636019299512092327020338426677133549564511

2048 bits: 32265694365222194010404357001516092548579199819041387945757267571596036749058634569094074219812846889534340995067820497901477561024599455565353002082511746648828169641181808973705035169234034211640728526085942856653459967866524633721100136389120826750971806555721953743512380362913169994078977035316885050734877880651635514708654045499243997726663832268601982453795322623327981372984678885139358313085521667255445647912968215291270713228333042612344810538357995867856503805643169118591231786654638431283960478897333710812694000748001860490290821407402203811181480383231178028186738528974827080974424570633369059334759

Last fiddled with by xilman on 2017-12-13 at 15:07 Reason: Wrap in [code] tags to reduce window width
CRGreathouse is offline   Reply With Quote
Old 2017-12-13, 07:01   #5
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

10128 Posts
Default

sorry it's 3 ^ [log_9 (N)] = sqrt (N).
but I will try again
Alberico Lepore is offline   Reply With Quote
Old 2017-12-13, 07:07   #6
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

I already have an exceptional idea
I'll write it in English tonight
Alberico Lepore is offline   Reply With Quote
Old 2017-12-14, 11:23   #7
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2×32×29 Posts
Default

A question.
This time I do not want to be wrong about computational complexity.
at each red line makes sqrt (N / 9)
What is its computational complexity?
thank you.
Attached Thumbnails
Click image for larger version

Name:	tree.jpg
Views:	176
Size:	8.7 KB
ID:	17336  
Alberico Lepore is offline   Reply With Quote
Old 2017-12-14, 12:35   #8
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

then there's another one.
at each red line makes sqrt (N)
What are the two computationalities?
Which is the fastest?
thank you
Attached Thumbnails
Click image for larger version

Name:	tree2.jpg
Views:	170
Size:	9.0 KB
ID:	17337  
Alberico Lepore is offline   Reply With Quote
Old 2017-12-14, 13:14   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

147608 Posts
Default

Alberico Lepore: Can you actually do some factorisations and prove what you are saying? Not using simple 3-digit numbers, but numbers that CRGreathouse posted.

Stop pretending and start doing.
retina is offline   Reply With Quote
Old 2017-12-14, 13:45   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
then there's another one.
at each red line makes sqrt (N)
What are the two computationalities?
Which is the fastest?
thank you
it would all depend on if the lines could be done in parallel for time complexity, the point being made is you have made a claim, and not supported it.
science_man_88 is offline   Reply With Quote
Old 2017-12-14, 15:03   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

17CD16 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
sorry it's 3 ^ [log_9 (N)] = sqrt (N).
but I will try again
I'm no expert, but sqrt(N) doesn't look a whole lot better than trial division.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Primality test based on factorization of n^2+n+1 carpetpool Miscellaneous Math 5 2018-02-05 05:20
20th Test of primality and factorization of Lepore with Pythagorean triples Alberico Lepore Alberico Lepore 43 2018-01-17 15:55
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm) Alberico Lepore Alberico Lepore 2 2018-01-01 21:31
14° Primality test and factorization of Lepore ( conjecture ) Alberico Lepore Alberico Lepore 48 2017-12-30 09:43

All times are UTC. The time now is 01:09.


Wed Nov 30 01:09:21 UTC 2022 up 103 days, 22:37, 0 users, load averages: 0.82, 0.85, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔