 |
|
| Science Forum Index » Math - Numerical Analysis Forum » (Sub)Primes between 10^12 and 10^18... |
|
Page 1 of 1 |
|
| Author |
Message |
| Adi... |
 Posted: Mon Oct 26, 2009 5:23 am |
|
|
|
Guest
|
Hi,
I have following problem:
I now that n (10^12 < n < 10^1 is a product of two primes n = p1 *
p2 (where 10^6 < p1,p2 < 10^9) or n is a prime. Is there any sure and
fast algorithm to decide wheater n is a prime or a subprime for these
conditions? If n is a subprime, I don't want to know factor, I'd like
only to know if it is a prime or subprime. I've heard about Miller-
Rabin test, but I know sometimes it gives me not true answer (not
prime or probably prime). |
|
|
| Back to top |
|
|
|
| user923005... |
| Posted: Mon Oct 26, 2009 4:24 pm |
|
|
|
Guest
|
On Oct 26, 8:23 am, Adi <adrian... at (no spam) gmail.com> wrote:
[quote]Hi,
I have following problem:
I now that n (10^12 < n < 10^1 is a product of two primes n = p1 *
p2 (where 10^6 < p1,p2 < 10^9) or n is a prime. Is there any sure and
fast algorithm to decide wheater n is a prime or a subprime for these
conditions? If n is a subprime, I don't want to know factor, I'd like
only to know if it is a prime or subprime. I've heard about Miller-
Rabin test, but I know sometimes it gives me not true answer (not
prime or probably prime).
[/quote]
Define 'subprime', I am not familiar with this term.
The range you describe is tiny. Any method can solve it quickly.
Suggestion:
Use Miller-Rabin first, to get "probably prime" candidates. Those
that fail are definitely composite.
Then use proof method (APR-CL, whatever) for those that pass.
For a general discussion, see:
http://cr.yp.to/primetests.html
http://primes.utm.edu/prove/index.html |
|
|
| Back to top |
|
|
|
| user923005... |
| Posted: Mon Oct 26, 2009 4:33 pm |
|
|
|
Guest
|
On Oct 26, 8:23 am, Adi <adrian... at (no spam) gmail.com> wrote:
[quote]Hi,
I have following problem:
I now that n (10^12 < n < 10^1 is a product of two primes n = p1 *
p2 (where 10^6 < p1,p2 < 10^9) or n is a prime. Is there any sure and
fast algorithm to decide wheater n is a prime or a subprime for these
conditions? If n is a subprime, I don't want to know factor, I'd like
only to know if it is a prime or subprime. I've heard about Miller-
Rabin test, but I know sometimes it gives me not true answer (not
prime or probably prime).
[/quote]
I guess that there is no fast algorithm if you need to examine the
whole range, or we would not see this Project Euler problem:
http://projecteuler.net/index.php?section=problems&id=187 |
|
|
| Back to top |
|
|
|
| Gordon Sande... |
| Posted: Tue Oct 27, 2009 6:38 am |
|
|
|
Guest
|
On 2009-10-26 23:24:55 -0300, user923005 <dcorbit at (no spam) connx.com> said:
[quote]On Oct 26, 8:23 am, Adi <adrian... at (no spam) gmail.com> wrote:
Hi,
I have following problem:
I now that n (10^12 < n < 10^1 is a product of two primes n = p1 *
p2 (where 10^6 < p1,p2 < 10^9) or n is a prime. Is there any sure and
fast algorithm to decide wheater n is a prime or a subprime for these
conditions? If n is a subprime, I don't want to know factor, I'd like
only to know if it is a prime or subprime. I've heard about Miller-
Rabin test, but I know sometimes it gives me not true answer (not
prime or probably prime).
Define 'subprime', I am not familiar with this term.
[/quote]
According to some citations from Google it is p-1. OP corrected
subprime to be semiprime which is pq where both p and q are prime
but not neccessarilly distinct (i.e. p=q is OK).
Google and subprime mostly yields stories about failing banks! :-(
[quote]The range you describe is tiny. Any method can solve it quickly.
Suggestion:
Use Miller-Rabin first, to get "probably prime" candidates. Those
that fail are definitely composite.
Then use proof method (APR-CL, whatever) for those that pass.
For a general discussion, see:
http://cr.yp.to/primetests.html
http://primes.utm.edu/prove/index.html[/quote] |
|
|
| Back to top |
|
|
|
| Adi... |
| Posted: Tue Oct 27, 2009 9:16 am |
|
|
|
Guest
|
Sorry, of course I mean semiprime :-)
Thanks a lot! |
|
|
| Back to top |
|
|
|
| Cristiano... |
| Posted: Tue Oct 27, 2009 12:36 pm |
|
|
|
Guest
|
Adi wrote:
[quote]I've heard about Miller-
Rabin test, but I know sometimes it gives me not true answer (not
prime or probably prime).
[/quote]
I don't know what "subprime" means, but the MR test can be always correct if
you choose the right bases. Take a look at the chapter 4, definition 4.29:
http://www.cacr.math.uwaterloo.ca/hac/
Cristiano |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 7:45 pm
|
|