Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working with the multiplicative ring of integers modulo $2^{127}$.

Consider the set $E=\{(k,l) \mid 5^k \cdot 3^l \equiv 1\mod 2^{127}, k > 0, l> 0\}$. I wonder if anybody knows or has an idea where to look for a result related to a lower bound for $M=\min\{k+l \mid (k,l)\in E \}$.

We have that $0<M\leq \mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)+\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)$ where $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)=2^{125}$ and $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)=2^{125}$ (orders of these primes in the multiplicative ring $\mathbb{Z}_{2^{127}}$).

I also would like to generalize the above for primes other than 5 and 3.

Is there a result about a tighter lower bound for $M$?

share|improve this question
    
P.S.: By the way, $k+l>1+1=2$ because $5\cdot 3=15\not \equiv 1 \mod 2^{127}$ and $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(15)=2^{123}$. Of course, I can program an algorithm that would search for the pair with smallest sum. But the search would have to be done with small bounds for $k$ and $l$ otherwise it would take unrealistic amount of time to finish. Even with these small bounds for $k$ and $l$, the algorithm may not give an answer if the values $k$ and $l$ with smallest sum are greater than the bounds used in algorithm. –  user129118 Feb 22 at 2:24
1  
This isn't a tight bound in either direction, but heuristically Birthday Paradox-style arguments suggest that after you've had roughly $\sqrt{2^{127}}\approx 2^{64}$ numbers of the form $5^k$ and the same number of numbers of the form $3^{-l}$ then you should expect a collision, and that you shouldn't expect a collision much before that point, so your $M$ should be in the general range of $2^{64}$ 'on average'. –  Steven Stadnicki Feb 22 at 2:56

3 Answers 3

up vote 3 down vote accepted
+50

Claim:

Let $c=40647290924413185736448652556727923386$, then the set of solutions is given by $$A = \{(k,l) \in (\Bbb Z/2^{126} \Bbb Z)^2 \mid 5^k3^l \equiv 1\bmod 2^{127}\}= \{(cn, 2 n) \mid n \in \Bbb Z\}$$

This gives an explicit formula for all solutions of $0\leq l+k < 2^{126}$, namely $$l+k = (2n \bmod 2^{126})+(cn \bmod 2^{126})$$ with $0<n<2^{125}$. I find it hard to calculate the minimum of that expression.

Reason:

The set $A = \{(k,l) \mid 5^k3^l \equiv 1\bmod 2^{127}\}$ can be interpreted as a subspace of $(\Bbb Z/2^{126} \Bbb Z)^2$. We only need to find a generator of that subspace to give an explicit characterization of $A$.

This is hard in general, but in the case of the modulus $2^{n}$ we can do the following: Given $k,l \in \Bbb Z/ 2^{n-1} \Bbb Z$ such that $5^k3^l \equiv 1 \bmod 2^{n}$ we also know that $5^k3^l \equiv 1 \bmod 2^{n-1}$. Conversely, given a solution to the second equation, we can try to lift $(k,l)$ from $ \Bbb Z/ 2^{n-2} \Bbb Z$ to $ \Bbb Z/ 2^{n-1} \Bbb Z$.

Now by consideration $\bmod \,2^3$ it is clear that both $k$ and $l$ are even. We can therefore lift a solution of $5^k3^2 \bmod 2^3$ (my little python code did that pretty instantly) to find that $$5^{c}3^2\equiv 1 \bmod 2^{127}$$ which is of order $2^{125}$ in $\Bbb Z/2^{126} \Bbb Z$ and therefore a generator of $A$.


EDIT: One can use continued fractions of $c/2^{m}$ to obtain small values of $(cn \bmod 2^{m})$ and thus also of $l+k$. The lowest I found so far is $$\begin{eqnarray} l&=&11726533429350798020\\ k&=&\;\,\;\;391079140617450804\\l+k&=&12117612569968248824<\sqrt{2^{127}}<2^{64}. \end{eqnarray}$$

share|improve this answer
    
I checked the results you obtained and they work. Thanks for that. But I have few questions about the way you obtained them. First, when you wrote "Conversely, given a solution to the second equation, we can try to lift $(k,l)$ from $\mathbb{Z}/2^{n-2}\mathbb{Z}$ to $\mathbb{Z}/2^{n-1}\mathbb{Z}$``. I don't see why it is true for mod $2^{n}$ for any $n$ positive integer. The other way around is true. –  user129118 Mar 28 at 6:35
    
Second, when obtaining the value of $c$ such that $5^{c}3^2\equiv 1 \bmod 2^{127}$, does your code search through all even numbers until it finds? I am not able to replicate your experiment (that is just because I'm good at programming). Finally, you mentioned that $5^{c}3^2\equiv 1 \bmod 2^{127}$ has order $2^{125}$. I think you meant that is the order of $5 \bmod 2^{127}$, right? –  user129118 Mar 28 at 6:35
1  
Let me adress your questions in two different comments: 1. You are right, we can't always lift a solution of from $\mod 2^{n-1}$ to $\mod 2^{n}$. That's why I said "try". However, it works sufficiently often that a little DFS gives the answer immediately: If $5^k3^2\equiv 1 \bmod 2^{n-1}$, try $5^k3^2$ and proceed recursively, if this fails try $k \to 2^{n-3}+k$. This works as a general method if we know that there must be a solution to $5^k3^2\equiv 1$. In this case we know by order arguments. –  benh Mar 28 at 7:24
1  
I hope the last comment also answered the first question of your second comment. Regarding the second question, I meant something else: Consider the set of all solutions $$G:=\{(k,l) \mid 5^k3^l \equiv 1 \bmod 2^{127}\},$$ then this set forms a subgroup $G\subset\Bbb Z /2^{126}\Bbb Z \times \Bbb Z/2^{126} \Bbb Z$. This subgroup $G$ is itself isomorphic to $\Bbb Z/2^{125} \Bbb Z$. Therefore it is enough to see that the element $(c,2)$ has order $\Bbb 2^{125}$ in $Z /2^{125}\Bbb Z \times \Bbb Z/2^{125} \Bbb Z$ to see that $(c,2)$ is a generator for $G$. –  benh Mar 28 at 7:29

Let $k=l=n$ so that $5^k3^l=15^n=(16-1)^n=(2^4-1)^n$. Now take $n=2^{123}$ and apply the binomial theorem, which gives all but the last two terms clearly divisible by $2^{127}$ and the last two terms are $$-2^{123}\cdot 2^4 +1,$$ which is $1$ mod $2^{127}.$ So here $k+l=2^{124},$ which is a fourth of the value ord(3)+ord(5).

Maybe a lower value can be obtained on using other imposed relations between the exponents $k,l.$

share|improve this answer
1  
@user129118 So the minimal $k+l$ is at most $2^{124}$... This seems like it might be way more than the actual minimum. I've looked at trying a pigeon-hole type argument on the set of $5^k3^l$ of which there are $2^{250}$ "pigeons", and only $2^{127}$ "holes", so some residue class gets a lot of pigeons in it, any two of which produce a solution to $5^k3^l=1$ mod $2^{127}.$ I don't know if this leads anywhere. –  coffeemath Feb 16 at 22:31
    
Oh, I understood that is not exactly a tight lower bound for $M$ but at least it decreased the upper bound. I will continue to look for some suitable lower bound. Thank you very much for the help. I hope anyone out there knows any result the can be applied to what I need. –  user129118 Feb 17 at 3:19

To flesh my 'birthday paradox' heuristic from a comment out into at least a partial answer:

The core concept is that among the first $m$ values of $5^k$ and the first $n$ values of $3^{-l}$, we have $mn$ different potential collisions, and if we treat these interactions as independent events then we should expect each of them to yield an actual collision with probability $2^{-127}$; this means that within approximately $2^{127}$ potential collisions we should expect an actual collision. Since $m+n$ is minimized for a given value of $mn$ when $m=n$, then we should expect the minimum value of $m+n$ to occur where $m\approx n$. Plugging this in to $mn\approx 2^{127}$ yields $m\approx n\approx 2^{64}$ and $m+n\approx 2^{65}$ (up to relatively small constant factors).

Of course, this is a heuristic argument, not an exact one; but as long as $m\gg \log_5 2^{127}\approx 55$ and $n\gg\log_3 2^{127}\approx 80$, then I would expect the sets $\{5^k\ |\ 0\leq k\lt m\}$ and $\{3^{-l}\ |\ 0\leq l\lt n\}$ to be roughly equidistributed mod $2^{127}$; since the numbers we're talking about are many orders of magnitude larger then this assumption seems reasonable.

Note that if the goal were to minimize $|k|+|l|$ then this heuristic argument can be extended to provide an explicit upper bound of $2\lceil\sqrt{2^{127}}\rceil$: among the $2^{127}$ values of $5^k3^l\bmod 2^{127}$ for $1\leq k\leq \lceil\sqrt{2^{127}}\rceil$, $1\leq l\leq \lceil\sqrt{2^{127}}\rceil$ there must (by the pigeonhole principle) be a collision, say $5^{k_0}3^{l_0} \equiv 5^{k_1}3^{l_1}$. Then dividing out, we obtain $5^{k_0-k_1}3^{l_0-l_1}\equiv 1$, where clearly $0\leq |k_0-k_1|\leq\lceil\sqrt{2^{127}}\rceil$, and likewise for the $l$ values. (This argument doesn't work for the actual problem, of course, because there's no guarantee that $k_0-k_1$ and $l_0-l_1$ have the same signs.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.