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

[Alberico Lepore]

Now place a decryptive paper.
To see if anyone can solve the problem

[CRGreathouse]

We start from a number N which has an unknown factorization N = a*b which we hope to discover. Your first step is computing the square root of (N-n*a)-(2*a-1) = a^2 - 2*a + 1. But we don't know the value of a, so how could we possibly find this?

[science_man_88]

Originally Posted by Alberico Lepore

Now place a decryptive paper.
To see if anyone can solve the problem

you typo a few words at very least. also the column that's supposed to sum the first column doesn't work out, so I'm lost. I can send you and email if needed for you to respond to this.edit: okay I can partially see how the table gets made.

[Alberico Lepore]

Originally Posted by CRGreathouse

We start from a number N which has an unknown factorization N = a*b which we hope to discover. Your first step is computing the square root of (N-n*a)-(2*a-1) = a^2 - 2*a + 1. But we don't know the value of a, so how could we possibly find this?

you are genius

https://www.wolframalpha.com/input/?...3D187+,+a%3D11

[CRGreathouse]

In other words, you'll ask Mathematica/WA to solve a Diophantine quadratic, which will eventually involve factoring the number you set out to factor.

[Alberico Lepore]

Hey @CRGreathouse I found a six-nary algorithm that at every level makes a square root.
Is it worth it to implement it?
What is its computational complexity?
It is fully functional.

[science_man_88]

Originally Posted by Alberico Lepore

Is it worth it to implement it?
What is its computational complexity?
It is fully functional.

you could always learn from implementing it, computational complexity can have two parts time and space, which one do you want to know. in this case do you mean functional as it works, or that it is purely based on functions.

[Alberico Lepore]

Originally Posted by science_man_88

you could always learn from implementing it, computational complexity can have two parts time and space, which one do you want to know. in this case do you mean functional as it works, or that it is purely based on functions.

Given a number N I have a six-nar tree that is, it has six branches and at each level it makes the square root of N.
How many levels of the tree will I have to go down as a function of N?

[science_man_88]

Originally Posted by Alberico Lepore

Given a number N I have a six-nar tree that is, it has six branches and at each level it makes the square root of N.
How many levels of the tree will I have to go down as a function of N?

depends on how many factors you plan on splitting off probably, also depends on how effective the algorithm is at factoring.

[Alberico Lepore]

Originally Posted by science_man_88

depends on how many factors you plan on splitting off probably, also depends on how effective the algorithm is at factoring.

suppose a semi-prime

[science_man_88]

Originally Posted by Alberico Lepore

suppose a semi-prime

would then depend on the algorithm. show it to us, if you want the numbers you seek.