Water-Jug and the diophantine equations!!?

Leave a comment

Many of you might have heard about the famous problem of water and jugs. It goes as follows:

There are n jugs each having particular capacity (all unique) and unlimited supply of water. The problem is to find whether a particular value, say w, be measured from the given jugs.

To make it simple, say there are 2 jugs of capacity 5L and 3L each. The problem is  to find whether 4L can be measured?

Well many of you know the solution, and it can be found at many of the places!!!

* Fill the 3l, pour into 5l

* Fill the 3l, pour into 5l (1l remaining in 3l jug)

* Empty the 5l an pour into it the water from 3l, that is 1l

* Fill the empty 3l and pour into 5l jug and done.

What to do with diophantine equations?

I am not sure!!! but this one could be possible.

Let the capacities be a,b,c,d and the final quantity to be measured be p, consider the following equation.

ax + by + cz + dw = p…………………….(1)

The result which I am not sure of (:D) :

The problem (of water – jug ) has a solution if (1) has solution. (1) has a solution only when gcd (s,b,c,d) = kp, where k = 1,2,3,4,..

How do I verify both problems are the same ??

   

How do I generate large primes???

Leave a comment

Many of the cryptography based techniques involves handling large numbers, specially large prime numbers. It is obvious from experience that our computers cannot handle such huge numbers(Here, huge refers to numbers involving 300 digits and even more!!!).

Set your computer for this task!!

There are many libraries and extensions out there to handle huge numbers. My choice from them is GNU Multiple Precision (GMP). It is very easy to understand and offers a lot of functionality including efficient number theoretic algorithms.

You can download gmp at this link. It is a library for C. It has its own data types(mpz_t, mpz_f etc.) defined in the library.

Using gmp in C may be a bit frustrating due to the data types and initialization of the declared variables. There is a python extension for this library: gmpy. This makes your task a lot easier.

Assuming, you have gmp and gmpy let us see how to generate large prime numbers.

There are few methods to generate(test, to be more precise) prime numbers apart from the trivial method of checking for its divisibility.

The available methods can be classified into two types:

1) Probabilistic

2)  Deterministic

1) Probabilistic: Algorithms falling in this category are probabilistic, in simple words they cannot be trusted. There is chance of the algorithms giving a wrong answer. Some of these are

a) Primality test based on Fermat’s little theorem

b) Solovay – Strassen test

c) Miller – Rabin Test

2) Deterministic approach: Algorithms of this class always give exact answers. There is no chance of error.

a) Algorithm due to AKS( Agarwal, Kayal, Saxena IIT Kanpur)

We heavily rely upon probabilistic test though we have an implementation for the deterministic test mentioned above. This is due to the fact that the running time of AKS is pretty huge.

Fermat’s little theorem by itself is not a very good method for testing primality because there are composite numbers which do satisfy the theorem.

Compared to Miller – Rabin, Solovay – Strassen has higher probability of error. Hence Miller – Rabin is used. More explanation regarding Miller – Rabin can be found here.

Following is a python program for Miller – Rabin Test:

Image

Image

More Explanation about the code in my upcoming posts.