- #1
stroustroup
- 14
- 0
Is there an algorithm which, given n, returns an integer x such that 2 has order n modulo x (i.e, 2^n = 1 mod x and n is the smallest positive solution)? Is there any such algorithm which runs faster than factoring n?
How can I find a x such that the order of 2 mod x is n?
- Thread starter stroustroup
- Start date
In summary, finding a number x such that the order of 2 mod x is n is significant in number theory and cryptography, allowing for efficient computation of discrete logarithms and playing a crucial role in security. The order of 2 mod x is always a factor of the multiplicative order of 2 mod x, and there are various algorithms and techniques for finding such a number x. This problem has applications in coding theory, error-correcting codes, and pseudorandom number generation, and is an active area of research in mathematics and computer science. It also has implications in other fields such as physics, biology, and economics.
- #2
jgens
Gold Member
- 1,593
- 50
How about x = 2n-1?
- #3
stroustroup
- 14
- 0
Well... this is much simpler than I expected 
I guess I should have thought a bit more before posting that... I was convinced this would involve some advanced math and big time complexity.
I guess I should have thought a bit more before posting that... I was convinced this would involve some advanced math and big time complexity.
What is the significance of finding a number x such that the order of 2 mod x is n?
Finding such a number x is important in number theory and cryptography, as it allows for efficient computation of discrete logarithms and plays a crucial role in the security of many cryptographic algorithms.
What is the relationship between the order of 2 mod x and the multiplicative order of 2 mod x?
The order of 2 mod x is the smallest positive integer n such that 2^n mod x is congruent to 1. The multiplicative order of 2 mod x is the smallest positive integer k such that 2^k mod x is congruent to 1 for all integers relatively prime to x. Therefore, the order of 2 mod x is always a factor of the multiplicative order of 2 mod x.
How can I efficiently find a number x such that the order of 2 mod x is n?
There are various algorithms and techniques for finding such a number x, including the use of primitive roots, prime factorization, and the Chinese Remainder Theorem. The most efficient method will depend on the specific values of n and x.
What are some applications of finding a number x such that the order of 2 mod x is n?
Aside from its importance in number theory and cryptography, this problem has applications in various areas such as coding theory, error-correcting codes, and pseudorandom number generation.
What is the current state of research on finding numbers x with a given order of 2 mod x?
This problem is an active area of research in mathematics and computer science, with ongoing efforts to develop more efficient algorithms and to understand the relationships between different values of n and x. There are also applications of this problem in other fields such as physics, biology, and economics, which continue to drive research in this area.
Similar threads
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
Linear and Abstract Algebra
-
General Math