1
$\begingroup$

I recently found a different method to compute prime number in $\mathcal O(\log(\log n))$ complexity. At present, that logic working fine for $300$ digits prime number, which I found on websites.I need to validate whether that logic will be working fine for a higher number of digits. At present, I have computed a prime number of $300\ 000$ digits(but I am not sure whether this would be valid),

My questions are:

  • Where can I find a prime number of higher digits i.e., more than $300\ 000$ digits?
  • Where can I validate $300\ 000$ digit prime number is valid one?
$\endgroup$
11
  • $\begingroup$ A method with this complexity would be sensational! Is $\log(\log(n))$ actually the complexity of the method ? $\endgroup$
    – Peter
    Commented Apr 4, 2018 at 13:13
  • $\begingroup$ With PFGW , you can check your number $\endgroup$
    – Peter
    Commented Apr 4, 2018 at 13:14
  • $\begingroup$ Find a new prime of the form given in this question : math.stackexchange.com/questions/2635516/… $\endgroup$
    – Peter
    Commented Apr 4, 2018 at 13:23
  • 4
    $\begingroup$ I hate to sound overly skeptical, but just printing $n$ out has complexity $O(\log n)$. How is your algorithm outputting the candidate prime numbers? $\endgroup$ Commented Apr 4, 2018 at 13:45
  • 3
    $\begingroup$ Oh, it's actually not clear to me whether you claim to have an algorithm that produces large primes, or whether the algorithm tests a given integer for primeness. Could you please clarify? $\endgroup$ Commented Apr 4, 2018 at 13:49

3 Answers 3

3
$\begingroup$

Check it with a table of Mersenne primes (e.g. http://oeis.org/A000043) or use provable primes (e.g. Maurer's method, see Alg. 4.62 in the Handbook of Applied Cryptography).

$\endgroup$
3
$\begingroup$

Primo does this. It only runs on Linux, if you don't have one at home you can just create a virtual machine and run it as guest within your current OS. There are various tests that Primo can perform, please read the documentation on the website in order to adapt it to your special case.

Please note that it will take very long to certify that a $3\times10^{6}$-digit number is prime. If you want to test your method on large numbers, take a much smaller one to begin with, i.e., with about $10^{3}$ or $10^{4}$ digits.

$\endgroup$
2
  • $\begingroup$ Thanks for your info. but as i have primo only supports 40000 digits, In the release document they have mentioned that as follows, v4.3.0 (February 21, 2018) Maximal size of candidates increased up to 132,928 bits (~ 40,000 decimal digits). $\endgroup$
    – ideano1
    Commented Apr 5, 2018 at 3:16
  • $\begingroup$ @ideano1 Oh, right, I didn't see that. I guess I never needed to go beyond 40k digits before... $\endgroup$
    – Klangen
    Commented Apr 5, 2018 at 6:11
2
$\begingroup$

From what you write I understand that you want to prove that your method is fine. It probably is if you checked up to 300, digits. But the only way to validate a method is by analysing it step by step and actually prove that it works. No matter how many digits you try, that will not be a proof that your method has no flaws.

$\endgroup$
1
  • 1
    $\begingroup$ A method with this complexity would be fantastic , if it actually works in most cases. Too nice that I can believe it. $\endgroup$
    – Peter
    Commented Apr 4, 2018 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .