# Tag Info

7

The answer to "can $S_b=S_{b'}$ for $b \neq b'$" is in the affirmative. This is checked fairly quickly by brute force. Let $b=100$ and $b'=001$ (as in your example). Then set $p_0=7$, $p_1=5$, $q_0=3$ and $q_1=2$. Now, S_b=q_1 p_0 p_0 + q_0 p_0 + q_0=2 \cdot 7 \cdot 7 + 3 \cdot 7+3=122 \\ S_{b'}=q_0 p_0 p_1 + q_0 p_1 + q_1=3 \cdot 7 \cdot ...

4

$347^{61}\equiv 7^{61}$ (modulo 10). $7^{61}=7\cdot 7^{60}=7\cdot 49^{30}\equiv 7\cdot (-1)^{30}$ (modulo 10). Hence the answer is $7$.

3

hint: $347 = 7 \pmod {10}, 7^4 = 1 \pmod {10}$

3

B × B = Y, so possibilities there are B Y 2 4 3 9 4 6 7 9 8 4 9 1 O × B = O (O $\neq$ 1) B O 2 x 3 5 4 x 7 5 8 x 9 5 O = 5, B is odd O + O + (carry ?) = E B Y O E 3 9 5 0 7 9 5 4 9 1 5 8 Next is M, from B × BOB: B Y O E M 3 9 5 0 1 7 9 5 4 x 9 1 5 8 x So now we have all we need: 3 5 3 x 3 5 3 ------------- ...

2

$$B = 3, O = 5, M = 1, A = 2, R = 4, L = 6, E = 0, Y = 9, I = 7$$

2

Caveat: did not carefully check, but I believe the following works. For $m$, from the description of the scheme $r = g^k \mod p$ and $s= k^{-1}(m+ar) \mod q$. Thus, for message $m^\prime \stackrel{\rm def}{=} mr$, you need to forge (mod $q$) $$r^\prime = g^{\ell}$$ with $\ell\in\mathbb{Z}_q^\ast$ and $$s^\prime = \ell^{-1}(m^\prime+ar^\prime) = ... 2 HINT : Let [n] be the last digit of n. Then,$$[7^1]=7,[7^2]=9,[7^3]=3,[7^4]=1,[7^5]=7,\cdots$$And 61\equiv 1\pmod 4. 2 Since (M,n)=1, Euler's Theorem gives you M^{\phi(n)}\equiv1(mod n). Since e and d are inverses (mod \phi(n)), then ed\equiv1(mod \phi(n)), which tells us \exists k such that ed=k*\phi(n)+1. Then$$(M^e)^d\equiv M^{ed}\equiv M^{k*\phi(n)+1}\equiv(M^{\phi(n)})^kM\equiv 1^kM\equiv M(mod\ n)$$. 2 "On the Randomness of Legendre and Jacobi Sequences", Ivan Damgård, CRYPTO 88. "Quantum algorithms for some hidden shift problems", Wim van Dam et al., SODA '03. "On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol", Mauduit and Sárközy, Acta Arithmetica 1997. From the van Dam article: "We conjecture that ... 2 p and q being two different primes, there exists two integers m,n such that$$ mp-nq=1 $$Your two equations can also be rewritten$$ C^d = M +\alpha p \\ C^d = M + \beta q $$Multiplying the first by -nq and the second by mp and summing them, we get$$ (mp-nq)C^d = (mp-nq)M + (\beta m-\alpha n)pq $$And now returning to a modular ... 2 M is an integer. Suppose X is some integer with the property that$$X\equiv M\bmod p,\qquad X\equiv M\bmod q.$$The Chinese remainder theorem then says that if Y is any integer such that$$Y\equiv M\bmod p,\qquad Y\equiv M\bmod q$$then Y\equiv X\bmod pq. But obviously, M is an integer with the property that$$M\equiv M\bmod p,\qquad M\equiv M\bmod ...

2

Magma says that $\# H(\mathbb{F}_{103})=104$ and $\# J(\mathbb{F}_{103})=10610$. Here is the code I used: P<x> := PolynomialRing(GF(103)); C := HyperellipticCurve(x^5+1); #C; J:=Jacobian(C); #J;

1

This test, in combination with the words "fool proof" indicate that it almost certainly came from the numberphile video about the AKS test. The method you show is presented, called the AKS test (which it isn't), is claimed to be very fast (which it isn't), and then implies that we had no other way of figuring this out before -- that this was a revolution in ...

1

Will try and clarify a bit in depth without fancy words some other folks answers. $347^{61} = (340+7)^{61}$ and we know from binomial theorem that all but the term $7^{61}$ will have at least one factor $34 \cdot 10$ in it. Now let us make a table of the powers of 7, saving only the last digit at each step, 1,7,4(9),6(3),2(1) We see that 7,9,3,1, is ...

1

I don't think there's a general way to find the length without also find the factors, but don't that stop you. If you have a "very efficient" algorithm to answer questions like What are the two primes with 232 and 269 digits whose product is such-and-such? then you can factor 500-digit semiprimes fast in general -- just run your algorithm 250 times in ...

1

For (2) and (3), I think you should be computing mod $n$, not mod $\phi(n)$. (Requiring verifiers to know $\phi(n)$ leaks too much information.) Otherwise (2) could work. For (3) you've also got some complication. Instead, make the observation that, if the signing scheme is simply raising to the $d$ power, then 8^d = (2^3)^d = 2^{3d} = 2^{d3} = (2^d)^3 ...

1

Presumably this coding matrix works on only two letters at a time and treats the standard basis as a=1, b=2, c=3, d=4, etc... So, two letters at a time try to encode a word. As an indirect example, suppose we wanted to encode the word "apples." Originally, I would think of "apples" as the string (1, 16, 16, 12, 5, 19) since it is the first letter, 16th ...

1

You have $m'\equiv mk \pmod p$. Multiply both sides by $k^{-1}$ to get $m' k^{-1} \equiv mk k^{-1} \pmod p$. On the other hand you have $kk^{-1}\equiv 1 \pmod p$. Multiply both sides by $m$ and you get $m kk^{-1}\equiv m \pmod p$. You end up with $m' k^{-1} \equiv mk k^{-1} \equiv m \pmod p$

1

You've got all the high points. Your description of (1) is fine. You've also got the high points for the signature. Alice sends $(h(m))^d$ as the signature. Since $d$ is possessed only by Alice, this is fine. Bill will then take the message $m$ and hash it using the same hash function $h$ to obtain $h(m)$. He then also takes the received $(h(m))^d$, ...

1

As you noted, there are no fourth roots of unity $\bmod q$, hence $a^2\equiv 1\pmod q$. Then $a^2\ne1$ implies $a^2\not\equiv 1\pmod p$, i.e., $a^2\equiv -1\pmod p$. Thus $p\mid a^2+1$ and certainly $p=\gcd(n,a^2+1)$.

Only top voted, non community-wiki answers of a minimum length are eligible