Minyanim and Mathematics: A protocol for anonymous counting.

In Judaism, many communal prayers require a minimum of ten people. This quorum is called a "minyan" which is often also used to mean a service in general. (In Orthodox Judaism, only Jewish adult males count for a minyam while in Conservative Judaism all Jewish adults count). However, certain liturgical elements on fast days (such as a Torah reading at the afternoon prayer) require not just ten present, but ten who are actually fasting.

However, people may not wish to advertise that they are not fasting even if they are willing to assist with the minyan. Moreover, even a very observant individual might have a reason not to fast and would not want people to know about it (such as a medical condition). This leads to the following problem: How do we determine how many people are fasting without requiring people to disclose whether or not they are fasting?

In a recent minyan I attended, this question was handled by the gabbai (the person in charge of running the minyan) asking everyone to close their eyes and hold up one hand if they were fasting. This is obviously unsatisfactory since the gabbai finds out who is fasting. One could suggest slips of paper or the like. but they could be easily connected to particular individuals. To make this problem interesting, it is helpful to assume that everyone knows the identity of the sender of any communication they receive. Is there a solution under which individuals' statuses remain private while the minyan is assured of 10 fasters?

Curiously the answer is yes albeit the solution is a bit cumbersome. Here's how: The gabbai picks a random integer (the distribution doesn't matter although in practice one might want a reasonable distribution that approximates a bell curve or an exponential distribution or something similar). The gabbai takes this integer and adds 1 to it if he is fasting. The gabbai whispers this number to another person. That person adds 1 to the total if he is fasting and similarly passes it on to another person. The last person gives his number to the gabbai. The gabbai now subtracts the random integer that they initially added. The total the gabbai has is the number of people fasting.

A few notes about this algorithm. First, it is important that, when the gabbai is picking a random integer, that every integer has some non-zero probability of being chosen. Consider, for example, what would happen if the gabbai was known to only pick positive integers. If the gabbai picks 1, the next person can tell if the gabbai is not fasting. Thus, the gabbai can never pick 1. But then, by the same logic, the gabbai won't be able to pick 2. Or 3. And so on. This problem is avoided if the gabbai can pick any integer whether or not it is positive.

There is also a degenerate case of if only the gabbia is fasting or only the gabbai is not fasting. In those cases, the exceptional individual can work out the status of everyone else.

The algorithm also assumes that people are not going out of their way to obtain information. If two people bracket a third and cooperate, they can figure out the middle person's status as a faster.

In fact, it turns out that it is possible to make a more sophisticated protocol that would prevent this and similar tricks. This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. Implementation also would require much more computation than can be done by hand.

Less intensive algorithms can be used to increase the number of people who must cooperate. It is, for example, an interesting exercise to construct a variation of the above such that finding out someone's status requires the cooperation of at least three people.

This algorithm in practice is cumbersome. Moreover, the goal it seeks to accomplish is minor since, if the fast day liturgy is used, those sections of the services actually need to be performed by people who are fasting. Thus, the gabbai will need to know the status of at least a few people. However, this algorithm has the slight advantage that, if there are not enough people to recite the fast day liturgy, then no one will know which people cause the deficiency.

Diffie-Hellman: How to share a secret with everyone listening.

This post is the third post of a series of three posts on why we care about prime numbers. The first entry gave an overview of primes. The second discussed the link between Mersenne primes and perfect numbers. This post will discuss practical applications of large prime numbers and provide a concrete example.

The main focus of this post is the Diffie-Hellman algorithm. Diffie-Hellman is a procedure whereby two people can have a conversation and at the end of the conversation they will share a secret number. The remarkable thing is that even if an eavesdropper hears the entire conversation, the eavesdropper will have no feasible way of figuring out the secret. . By repeating this procedure many times two people develop can have a list of secret numbers which they can use to encrypt messages to each other that only they can read. As is standard in cryptography, I will refer to three people, Alice and Bob who want to share a secret number and Eve the evil eavesdropper wishes to obtain their secret number.

There is a standard analogy in cryptographic circles to accomplish this sort of task. Suppose Alice and Bob want to exchange an object through a mail system that they don't trust. But they know the mail employees aren't going to be able to get into a locked box. How can Alice send an object to Bob? She cannot just send a locked box because Bob won't have a key. Nor can she send a box and a key because then the corrupt mailmen can use the key to open the box. Here is the solution: Alice puts her object into the box and locks it with her lock. She mails this to Bob. Bob puts a second lock on the box and mails it back to Alice. Alice now removes her lock and sends it back to Bob. Bob can now remove his own lock and gain access to the contents of the box.

Before we discuss this algorithm in detail we need a few small mathematical facts. We call doing arithmetic where we only care about the remainder when divided by k to be “arithmetic mod k”. So for example, 4+6= 3 mod 7 since 4+6 = 10 and the remainder of 10 when divided by 7 is 3. For a concrete analog, when we tell what time it will be on a clock some number of hours from now we are doing arithmetic mod 12.

Now, we need to define a primitive root: Suppose for a fixed prime p we have some u such that u¹ u² u³ u⁴… u^p-1 mod p cycle through 1,2,3,4… p-1 in some order then we say that u is a primitive root for p. For example, if p=5, then 2 is a primitive root for 5 since 2¹=2,2²=4,2³=3,2⁴=1. But 4 is not a primitive root for 5 since 4¹=4, 4²=1,4³=4,4⁴=1 so we only cycled through 1 and 4. Now, it happens that every prime p has some primitive root u. The proof will not be given here but this fact is the only piece of non-trivial number theory we will need for this procedure.[1]

The last detail we need is to note how it is possible to quickly raises numbers to large powers. Naively, if I want to calculate xⁿ for some fixed x and large integer n I need to multiply by x n times. And this applies if I am operating mod k also. But we have a nice trick called repeated squaring that allows us to get around this. Observe that if we know x^y then we can calculate x^2y by squaring x^y. Thus, we can easily calculate x², x⁴, x⁸, x¹⁶ all the way up to the largest power of 2 less than n. Then we can write n in base 2 and calculate x^y in the obvious fashion by multiplying together the relevant powers of the form x^{2^t}. Thus, calculating xⁿ takes at most c log n multiplications for some fixed constant c.

We are now ready to outline the procedure. Alice says to Bob: Hey Bob, I want to talk to you. Let’s use Diffie-Hellman. Bob says ok and picks a large prime p (by large probably in the order of 100s of decimal digits) and Bob finds a primitive root u for this prime. Bob then picks a random positive integer between 1 and p-1, call it b. Bob calculates B = u^b mod p which is easy to calculate by our above remark. Bob then transmits B, p and u to Alice. Alice picks some a and calculates A = u^a mod p and sends A to Bob. Alice calculates S = B^a = (u^b)^a = u^ab mod p and Bob calculates by taking A^b mod p. Alice and Bob now share S. However, suppose we have our evil eavesdropper Eve. What information does she have? She has A. She has B. She has u and she has p. There’s no obvious way for Eve to work out u^ab mod p. If Eve had a fast way of finding a or b from knowing u^a=A mod p she’d be set. But that turns out to be quite hard. This problem, known as the discrete log, is very difficult in general. So Eve is stuck. Alice and Bob can construct an agreed upon code by repeatedly using this procedure and there’s nothing Eve can do about it. If Alice and Bob set p to be a few hundred digits than the computation necessary for Eve to work out what S is turns out to be more than all the computational power on Earth today.

Let's do a small example with Say p=17 and u=3. Bob says "My prime is 17, my primitive root is 3." Bob picks 6 as his random number. Bob calculates that 3⁶ mod 17 which is 15. So he says "my B is 15."

Alice picks a random number, say 13 and calculates 3¹³ mod 17 which is 12 so she says "My A is 12.".

Bob then calculates A^b mod 17, which is 12⁶ mod 17 which is 2. Alice calculates B^a mod 17 which is 15¹³ mod 17 which is 2

So Alice and Bob now share the secret number S = 2. Obviously, for 17 it isn’t that hard for Eve to work out the answer. She just needs to write out a table of powers of 3 mod 17. But if instead of 17 she had to deal with a prime that was a few hundred digits long that strategy would never work; Eve's table would have more entries in it than the number of atoms in the universe. There are other strategies Eve could try to attack this but in general she doesn’t have many options.

An important caveat: No one knows a quick way of doing the discrete log but it has not yet been proven that there is no quick way to do so. Almost everyone who has studied the problem is very sure that there isn’t a quick way.

Diffie-Hellman turns out to have a variety of practical problems with implementation. So more often a related algorithm called RSA is used instead. In a later post, I will discuss RSA. RSA has even more counter-intuitive properties than Diffie-Hellman. While Diffie-Hellman required Alice and Bob to be work with each other, in RSA the intended recipient simply needs to publish a key which can then be used by anyone to encrypt messages such that only the recipient can read them. The standard analogy used by cryptographers to describe this procedure of a box that anyone is able to lock but only the person with a special key can unlock. The fact that this is mathematically doable turns out to be very useful. Readers have likely used RSA without even realizing it if they have engaged in almost any form of commerce over the internet. Modern web browsers and other software implement RSA in a way that is invisible to casual user. Even though one does not notice it RSA is responsible for keeping credit card numbers and similar data to safe and secure.

Both Diffie-Hellman and RSA rest heavily on the ability to find large primes. Moreover, the security of these algorithms is connected strongly to our understanding of prime numbers and their properties. Thus, the mathematics of large primes is vital to the functioning of the modern economy.

Edit: Added the locked box analogy.

---

[1] In fact we won’t really need that fact other than that we need in the procedure access to a prime that has a primitive root and we want to know that there are large primes with this property. Since all primes have this property, so do all large primes.

Large Primes and Mersenne Primes

In the last two months, two new Mersenne Primes have been discovered. Mersenne Primes are prime numbers that are 1 less than a power of 2. So for example, 7 is a Mersenne prime. These two new primes 2^43,112,609-1 and 2^37,156,667-1 are the 45^th and 46^th Mersenne primes known and are the two largest primes known. Their discovery has made it into the popular press and has prompted multiple people to ask me what the big deal is and why mathematicians care about big primes anyways. This blog entry will be the first of three entries in which I will attempt to discuss these issues.

First, note that there are infinitely many prime numbers. This has been known since the ancient Greeks. An elegant proof is given by Euclid which I sketch out here: Assume I have a finite list of primes, p₁, p₂, p₃….p_n .If I take their product and add 1 I get p₁p₂p₃….p_n +1 and this number is clearly not divisible by any of the primes on my list. If this number is prime then I have a new prime that was not on my list. If this number is not prime then its smallest divisor that is not 1 must be a prime not on this list. Thus, for any finite list of primes I can always construct a new prime not on the list. There is a common misconception that if one takes , p₁, p₂, p₃….p_n to be the first n primes then it p₁p₂p₃….p_n +1 must itself be a prime. The smallest one where it does not lead to a prime is 2*3*5*7*11*13+1=59*509.

Unlike with generic primes, no one knows if there are infinitely many Mersenne primes. It is strongly believed that there are infinitely many but there is no proof as of yet. Mersenne primes are independently interesting for a variety of reasons. First, there is the issue of whether or not there are infinitely many. Second, Mersenne primes correspond to even perfect numbers. A number is said to be perfect if you add up all the positive divisors less than the number and end up with the number. So for example 6=1+2+3 so 6 is perfect. Euclid showed that for every Mersenne prime you could construct an even perfect number from it. Euler showed that the only even perfect numbers are those from Euclid's construction. Thus, information about Mersenne primes is information about perfect numbers, and discovering a new Mersenne prime leads to a new perfect number. I will discuss this in more detail in my next blog entry on this subject.

Third, Mersenne primes are interesting because there are tricks to test whether a number of the form 2^n-1 is prime that make it much easier to check whether such numbers are prime than a generic number. Thus, for most of the last 100 years the largest primes known have been Mersenne primes.

Now, why do we care about finding large primes? One simple reason is for the same reason that scientists might try to construct larger and larger atoms or might look for new species; because they are there, learning is fun, and you don't know what you might find.

Also, in a more general setting primes (although generally primes much smaller than Mersenne primes) are useful for cryptography which are used in many modern software applications. Many readers have likely used those cryptographic protocols without even realizing it when you've logged onto to secure websites and such.

Modern browsers handle the procedures for you automatically. So the ability to find large primes and related procedures (such as theability to factor large numbers quickly) are very relevant to the functioning of the modern economy as well as to various national security issues. I will discuss this cryptographic use of large primes in the third blog entry in this series.