# Parallel discrete logs (continues: modular arithmetic)

• CRGreathouse
In summary, The conversation revolves around finding discrete logarithms in GF(p) for a given n and odd prime p. There are many algorithms for this task, some designed for multiple queries. The speaker, however, has the opposite problem of having only one n value but multiple odd primes p. They have been using primes up to 10 million to 60 million but hope to increase this range. They are using sequential primes and can use a sieve to quickly factor p-1. The problem they are working on allows for some gaps in the calculations and a rare response of "unknown" would not be harmful. The speaker is implementing the baby-step giant-step algorithm and has set it to run on a huge problem size of primes up to
CRGreathouse
Homework Helper
I'm working on a problem that involves calculating many discrete logarithms in GF(p): given n and an odd prime p, either find a k with $2^k\equiv n\pmod p$ or return "failure" if no such k exists. Now there are many algorithms for computing discrete logarithms, some of which are designed for many queries: precalculations are done on a given p which allow queries for each n to be done quickly.

I have the opposite problem: one n value (say, -2131) but many odd primes p. In particular, I have been using the odd primes up to 10 million to 60 million. (I hope to increase this range dramatically, but current methods are too slow.)

Because I'm using sequential primes, I could if desired factor p-1 (or other terms) quickly with a sieve. Certain other calculations that are conventionally 'hard' become easy with such small moduli. In particular, since all numbers I use fit into a single machine word, multiplication is fast relative to its normal cost in multiprecision.

Further, the problem I'm working on has tolerance for gaps. A rare response of "unknown" from the algorithm would not be harmful. Each prime p for which I compute the discrete log contributes 'value' for the problem inversely proportional to the order of 2 mod p, so doubling the speed at the cost of 10% "unknown" values would be worthwhile.

Being wholly ignorant of the subtleties of the various algorithms I've seen, I thought to implement the baby step giant step algorithm to see how long it takes. The memory shouldn't be an issue, I hope -- for primes under a billion it should fit in my 128 kB L1 cache. (Unless I have 64 kB, in which case perhaps it is an issue.) The number field sieve methods seem to be (1) hard to code and (2) too slow for small primes, but the other ones I'm not sure about. Does anyone have experience here?

OK, I've implemented a basic version of the baby-step giant-step algorithm. It was actually a bit more complicated than I'd hoped: while it's a simple thing of itself, making it run in my program required a number of other changes.

I've set it to run on a huge problem size: the primes up to 500 million. This means 26 million discrete logarithm problems with prime moduli of 8-9 digits. Fortunately the lookup tables aren't bad at all, 90 kB in the worst case.

I inadvertently left the 'sanity checks' in the program, which check the discrete log after calculating it. While it will slow the program down slightly, it'll be nice to know it worked properly if that doesn't fire.

Any thoughts from someone who's actually used or coded some kind of discrete log program would be welcome. Heck, any comments would be appreciated period -- sometimes a second look can tell a lot, and I can miss obvious stuff. ;)

## 1. What is the concept of parallel discrete logs?

Parallel discrete logs is a method for solving the discrete logarithm problem in a more efficient way by using multiple processors or computing units to perform calculations simultaneously.

## 2. How does parallel discrete logs utilize modular arithmetic?

Modular arithmetic is used in parallel discrete logs to reduce the size of the numbers being computed, making them more manageable for parallel processing. This is done by reducing the numbers to their remainders when divided by a chosen modulus.

## 3. What are the advantages of using parallel discrete logs?

The main advantage of parallel discrete logs is its ability to significantly speed up the computation of discrete logarithms. This can be especially useful in cryptography applications where large numbers need to be computed quickly and securely.

## 4. Are there any limitations to using parallel discrete logs?

One limitation of parallel discrete logs is that it requires a significant amount of computing power and resources. This may not be feasible for smaller or less well-funded organizations. Additionally, it may not be suitable for all types of problems, as some may not benefit from parallel processing.

## 5. How is parallel discrete logs related to other mathematical concepts?

Parallel discrete logs is closely related to other mathematical concepts such as number theory, modular arithmetic, and cryptography. It also has applications in various fields such as computer science, physics, and engineering.

• Linear and Abstract Algebra
Replies
17
Views
4K
• Calculus and Beyond Homework Help
Replies
16
Views
1K
• Differential Equations
Replies
3
Views
2K
• Calculus
Replies
2
Views
2K
• Programming and Computer Science
Replies
9
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Math Proof Training and Practice
Replies
61
Views
6K
• Linear and Abstract Algebra
Replies
1
Views
3K
• Linear and Abstract Algebra
Replies
11
Views
5K
• Calculus and Beyond Homework Help
Replies
10
Views
2K