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

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

[science_man_88]

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?

proof of concept without the download and translation ...

[Alberico Lepore]

tomorrow night.
now in Italy it's late.
try to understand

[CRGreathouse]

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.

64 bits: 12948110090585311979

128 bits: 191875610236165000493961741999993232961

256 bits: 104346515658715073236701578230537664345079731008268447250755923399969554554527

512 bits: 8877405418354614101337795613309676609673488389927337368943966383733022288825857519728174752110656132115481773164541042027077109668409285166080822943514087

1024 bits: 110017842535385107563795555661123030649928671048545795736220084126740077360535371108397605185633055628612036218921956452272449040580855582723250597770349258450200896920600054607239415068082852975938869913095282502118922681797947602970968857144251026353070249934660110636019299512092327020338426677133549564511

2048 bits: 32265694365222194010404357001516092548579199819041387945757267571596036749058634569094074219812846889534340995067820497901477561024599455565353002082511746648828169641181808973705035169234034211640728526085942856653459967866524633721100136389120826750971806555721953743512380362913169994078977035316885050734877880651635514708654045499243997726663832268601982453795322623327981372984678885139358313085521667255445647912968215291270713228333042612344810538357995867856503805643169118591231786654638431283960478897333710812694000748001860490290821407402203811181480383231178028186738528974827080974424570633369059334759

[Alberico Lepore]

sorry it's 3 ^ [log_9 (N)] = sqrt (N).
but I will try again

[Alberico Lepore]

I already have an exceptional idea
I'll write it in English tonight

[Alberico Lepore]

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.

[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

[retina]

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.

[science_man_88]

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.

[Dr Sardonicus]

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.