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 20A16 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
Dumbassville

26·131 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 3·1,993 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 2·32·29 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 23×283 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
Dumbassville

26·131 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

583410 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 18:03.

Sun Jul 3 18:03:22 UTC 2022 up 80 days, 16:04, 0 users, load averages: 1.28, 1.54, 1.53