Tell me more ×
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.
up vote 0 down vote favorite

Given $a,b$ in $Z_N$* for some composite positive integer N. Let the bit sizes are $a_N , b_N , N_N$ respectively.

Also $a_N = (N_N$ or $N_N-1) , a<N , (a,N)=1$

$ b_N = (N_N$ or $N_N-1) , b<N , (b,N)=1$

select $t$ where $(t,N)=1$ and $0<t<N$ such that if $(a*t)≡(u)mod(N)$, $(b*t)≡(v)mod(N)$ then the output pair $(u,v)$ should have the bit sizes $0<v_N<{N_N\over2}$ and $0<u_N<{N_N\over4}$ respectively. any other values are not accepted

The attempt i tried to solve. -- Since given $a,b$ and $t$ can be any value within $N$ , I took $u$ value satisfying the condition $0<u_N<{N_N\over4}$ to get $t$, i.e, $t≡(a^{-1}*u)mod(N))$, then substituted it in second congruence equation $(b*t)≡(v)mod(N)$ to get $v≡(a^{-1}*u*b)mod(N)$. But it seems the realtion does not guarantee the size of $v_N$ to be within $0<v_N<{N_N\over2}$ for any $u$ selected in $0<u_N<{N_N\over4}$.

I know i did a mistake somewhere but unable to recognize it. So the question is , Is there any possible pair of $(u_N,v_N)$ that satisfies the given congruences and bit relations. If exists , is there any easy way to find $v$ for corresponding valid $u$ taken.

Please suggest me an idea to solve the problem. or someone solve it for me.

share|improve this question
The problem is not clear. What is given? What is to be determined? It looks like $b$, $t$, and $N$ are given, in which case $v$, which is $bt$ reduced modulo $N$, is completely determined, and there is no reason to think it will be small compared to $N$. – Gerry Myerson Feb 4 at 9:14
@Grerry Myerson : yes, $v$ compared to $N$ is small, but my condition is $t$ should be in such a way that , the bit size of $v$ is in range $0<v_N<{N_N\over2}$ and $(a*t)\equiv u \pmod N$ where $0<u_N<{N_N\over4}$. If you carefully observer though the values of $u,a,b,t,N$ are already determined, They have to be selected carefully, such that all the conditions should be satisfied – user1665835 Feb 4 at 9:24
Given $a$, $b$, and $N$, you want $t$ such that (roughly speaking) $at$ reduced modulo $N$ is less than $\sqrt N$ and $bt$ reduced modulo $N$ is less than $\root4\of N$. I don't think this is always possible. I think there's a theorem of Thue that lets you get both of them down to $\sqrt N$, but that's it. By the way, your first comment broke the formatting. I'd recommend deleting it. – Gerry Myerson Feb 4 at 12:04
The Thue theorem isn't exactly as I remembered it but may still be helpful. See math.uga.edu/~pete/Brauer-Reynolds51.pdf – Gerry Myerson Feb 4 at 12:10

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.