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

2017-12-14, 15:36   #12
Alberico Lepore

May 2017
ITALY

2·32·29 Posts

Now place a decryptive paper.
To see if anyone can solve the problem
Attached Files
 12° Primality test and factorization of Lepore_for_mersenne.pdf (34.5 KB, 155 views)

 2017-12-14, 20:20 #13 CRGreathouse     Aug 2006 5,987 Posts 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?
2017-12-14, 20:44   #14
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2017-12-14 at 20:47

2017-12-14, 20:53   #15
Alberico Lepore

May 2017
ITALY

52210 Posts

Quote:
 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

 2017-12-14, 21:12 #16 CRGreathouse     Aug 2006 135438 Posts 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.
 2017-12-16, 14:29 #17 Alberico Lepore     May 2017 ITALY 2×32×29 Posts 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.
2017-12-16, 15:19   #18
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 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.

2017-12-16, 15:22   #19
Alberico Lepore

May 2017
ITALY

2·32·29 Posts

Quote:
 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?

2017-12-16, 15:28   #20
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 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.

2017-12-16, 15:37   #21
Alberico Lepore

May 2017
ITALY

2·32·29 Posts

Quote:
 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

2017-12-16, 15:53   #22
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

Quote:
 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.

 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 19:50.

Wed Feb 8 19:50:12 UTC 2023 up 174 days, 17:18, 1 user, load averages: 0.86, 0.85, 0.90