Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Question

Expand Messages
  • Alan Eliasen
    ... Regan, Yes, Java already has built-in methods to do this for you. For example, the constructor: BigInteger(int bitLength, int certainty, Random rnd)
    Message 1 of 64 , Oct 5, 2004
    • 0 Attachment
      regan cheng wrote:
      > SIr/Madam
      >
      > 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?

      Regan,

      Yes, Java already has built-in methods to do this for you. For example,
      the constructor:

      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,
      Random rnd)

      "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
      arbitrarily low.

      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
      BigInteger provides.

      --

      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
    • Kermit Rose
      ... Thank you David. 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
      Message 64 of 64 , Oct 20, 2012
      • 0 Attachment
        On 10/20/2012 10:07 AM, primenumbers@yahoogroups.com wrote:
        > 2.2. Re: Question
        > 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
        >
        > David

        Thank you David.

        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.

        Kermit








        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.