Blum Blum Shub Random number generation algorithm

class generator {

      // Two prime numbers //

      double p=11.0;

      double q=19.0;

      // local loop variable //

      int i=0;

      double x=0;

      // result container //

      double randomNumber = 0.0;

      // empty constructor //

      public generator()

            {

            }    

      public void getRandomNumbers(int seed,int numbers)

            {

                        x = seed;

                        for(i=0;i<numbers;i++)

                        {

                                          // BBS random number generation equation //

                                          randomNumber = (x*x)%(p*q);

                                          // showing the resulant number on screen //

                                          System.out.println(randomNumber);

                                          // result Xn number swap //

                                          x = randomNumber;    

                        }

            }

}

public class blumBlumShubAlgorithm {

      public static void main(String args[])

            {

                  // Creating an instance and calling the method to generate numbers //

                  (new generator()).getRandomNumbers(1298, 500);

            }

}

Brent's algorithm

Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. However, it is based on a different principle: searching for the smallest power of two 2ⁱ that is larger than both λ and μ. For i = 0, 1, 2, etc., the algorithm compares x₂ⁱ₋₁ with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length λ of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of ƒ rather than three.

The following Python code shows how this technique works in more detail.

def brent(f, x0):

    # main phase: search successive powers of two

    power = lam = 1

    tortoise = x0

    hare = f(x0)  # f(x0) is the element/node next to x0.

    while tortoise != hare:

        if power == lam:  # time to start a new power of two?

            tortoise = hare

            power *= 2

            lam = 0

        hare = f(hare)

        lam += 1

    # Find the position of the first repetition of length lambda

    mu = 0

    tortoise = hare = x0

    for i in range(lam):

    # range(lam) produces a list with the values 0, 1, ... , lam-1

        hare = f(hare)

    while tortoise != hare:

        tortoise = f(tortoise)

        hare = f(hare)

        mu += 1

    return lam, mu

Tortoise and hare

Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...

Floyd's cycle-finding algorithm, also called the "tortoise and the hare" algorithm, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The algorithm is named for Robert W. Floyd, who invented it in the late 1960s

The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, x_i = x_i + kλ, where λ is the length of the loop to be found. In particular, whenever i = mλ ≥ μ, it follows that x_i = x_2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value x_μ in the sequence, using the fact that λ divides ν and therefore that x_μ = x_{ν + μ}. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which x_{μ + λ} = x_μ.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at x_i, and the other (the hare) at x_2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.

The following Python code shows how this idea may be implemented as an algorithm.

def floyd(f, x0):

    # The main phase of the algorithm, finding a repetition x_mu = x_2mu

    # The hare moves twice as quickly as the tortoise

    # Eventually they will both be inside the cycle

    # and the distance between them will increase by 1 until

    # it is divisible by the length of the cycle.

    tortoise = f(x0) # f(x0) is the element/node next to x0.

    hare = f(f(x0))

    while tortoise != hare:

        tortoise = f(tortoise)

        hare = f(f(hare))

    # at this point the position of tortoise which is the distance between

    # hare and tortoise is divisible by the length of the cycle.

    # so hare moving in circle and tortoise (set to x0) moving towards

    # the circle will intersect at the beginning of the circle.

    # Find the position of the first repetition of length mu

    # The hare and tortoise move at the same speeds

    mu = 0

    tortoise = x0

    while tortoise != hare:

        tortoise = f(tortoise)

        hare = f(hare)

        mu += 1

    # Find the length of the shortest cycle starting from x_mu

    # The hare moves while the tortoise stays still

    lam = 1

    hare = f(tortoise)

    while tortoise != hare:

        hare = f(hare)

        lam += 1

    return lam, mu

This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses O(λ + μ)operations of these types, and O(1) storage space.

Brent's algorithm

Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. However, it is based on a different principle: searching for the smallest power of two 2ⁱ that is larger than both λ and μ. For i = 0, 1, 2, etc., the algorithm compares x₂ⁱ₋₁ with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length λ of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of ƒ rather than three.

The following Python code shows how this technique works in more detail.

def brent(f, x0):

    # main phase: search successive powers of two

    power = lam = 1

    tortoise = x0

    hare = f(x0)  # f(x0) is the element/node next to x0.

    while tortoise != hare:

        if power == lam:  # time to start a new power of two?

            tortoise = hare

            power *= 2

            lam = 0

        hare = f(hare)

        lam += 1

    # Find the position of the first repetition of length lambda

    mu = 0

    tortoise = hare = x0

    for i in range(lam):

    # range(lam) produces a list with the values 0, 1, ... , lam-1

        hare = f(hare)

    while tortoise != hare:

        tortoise = f(tortoise)

        hare = f(hare)

        mu += 1

    return lam, mu

Like the tortoise and hare algorithm, this is a pointer algorithm that uses O(λ + μ) tests and function evaluations and O(1) storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the Pollard rho algorithm by around 24%. He also performs an average case analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.

 SOURCE 

// Read more at http://en.wikipedia.org/wiki/ //