mersenneforum.org Factorization and primality test O([log_9(N)]^3)
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-12, 20:44 #1 Alberico Lepore     May 2017 ITALY 2×32×29 Posts 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?
2017-12-12, 21:38   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by Alberico Lepore 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?

 2017-12-12, 21:49 #3 Alberico Lepore     May 2017 ITALY 2·32·29 Posts tomorrow night. now in Italy it's late. try to understand
 2017-12-13, 06:25 #4 CRGreathouse     Aug 2006 5,987 Posts 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
 2017-12-13, 07:01 #5 Alberico Lepore     May 2017 ITALY 10128 Posts sorry it's 3 ^ [log_9 (N)] = sqrt (N). but I will try again
 2017-12-13, 07:07 #6 Alberico Lepore     May 2017 ITALY 2·32·29 Posts I already have an exceptional idea I'll write it in English tonight
 2017-12-14, 11:23 #7 Alberico Lepore     May 2017 ITALY 2×32×29 Posts 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
 2017-12-14, 12:35 #8 Alberico Lepore     May 2017 ITALY 2·32·29 Posts 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
 2017-12-14, 13:14 #9 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 147608 Posts 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.
2017-12-14, 13:45   #10
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by Alberico Lepore 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.

2017-12-14, 15:03   #11
Dr Sardonicus

Feb 2017
Nowhere

17CD16 Posts

Quote:
 Originally Posted by Alberico Lepore 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 5 2018-02-05 05:20 Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 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