Re: [PrimeNumbers] Question
- regan cheng wrote:
> I would like to ask if there is a way on how to generate 100 digits
> prime numbers with the use of Java?
> One thing i had read about prime number is that if your looking for
> 100 digits prime numbers you would need to randomize
> the 100 digits number and come up with a primarity rule to check if
> the number is prime. Is this algorithm applicable in generating a
> 100 digits prime number?
Yes, Java already has built-in methods to do this for you. For example,
BigInteger(int bitLength, int certainty, Random rnd)
"Constructs a randomly generated positive BigInteger that is probably prime,
with the specified bitLength."
Note that the length is in bits. Preferably, use the method:
public static BigInteger probablePrime(int bitLength,
"Returns a positive BigInteger that is probably prime, with the specified
bitLength. The probability that a BigInteger returned by this method is
composite does not exceed 2^-100."
Note that these are probabilistic tests, but the probability of error is
so low that if you generated random numbers for your entire lifetime, the
odds against you getting a composite are still miniscule.
You can, of course, also implement these tests by hand. BigInteger has
an isProbablePrime method, which lets you set the probability of error to be
Keep in mind that old versions of Sun's Java release had a bug in their
implementation of the Lucas test, which caused errors when testing large
numbers. This has been fixed for some years now.
You can also implement primality tests yourself. I've implemented
Rabin-Miller primality testing, and it's quite simple using the methods that
Alan Eliasen | "Whenever you find you are on the side of
eliasen@... | the majority, it is time to pause and
http://futureboy.homeip.net/ | reflect." --Mark Twain
- On 10/20/2012 10:07 AM, email@example.com wrote:
> 2.2. Re: QuestionThank you David.
> Posted by: "djbroadhurst"d.broadhurst@... djbroadhurst
> Date: Fri Oct 19, 2012 9:02 am ((PDT))
> --- Inprimenumbers@yahoogroups.com,
> Kermit Rose<kermit@...> wrote:
>> >Methods to solve Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0
>> >for what values of x would
>> >x^2 + 5 x + 6 be a perfect square.
> Set A = 1, B = 0, C = -1, D = 5, E = 0, F = 6.
> and you will get the obvious answer from Dario:
> x = -2
> y = 0
> and also:
> x = -3
> y = 0
> Calculation time: 0h 0m 0s
I had been confused by consideration of the following:
if x y = z and y > x,
then if we set t = (y+x)/2 and s = (y-x)/2
then z = t^2 - s^2
and x = y - 2 t.
So z = x y = (y - 2t) y = y^2 - 2 t y
y^2 - 2 t y - z = 0
Transforming w = y - k yields
(w + k)^2 - 2 t (w + k) - z = 0
w^2 + (2 k - 2 t) w + (k^2 - 2 t k - z) = 0
which has integral solution if and only if
(2k - 2 t)^2 + (z + 2 t k - k^2) is an integral square
In all that derivation, I forgot that I still did not know what value t was.
I confused myself too easily.
[Non-text portions of this message have been removed]