Wikipedia:Reference desk/Archives/Mathematics/2018 June 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 25

Meaning of $A(B^{-1}~{mod}~M)$?

I'm confused. Is the above equivalent to $A/(B~{mod}~M)$ or what? Earl of Arundel (talk) 18:02, 25 June 2018 (UTC)

Depending on context, it is possibly a typo (either yours, or the original's). Where did you find it? --JBL (talk) 19:17, 25 June 2018 (UTC)

From the Blum–Goldwasser Cryptosystem article:

Alice receives $(c_{0},\dots ,c_{L-1}),y$. She can recover $m$ using the following procedure:

1. Using the prime factorization $(p,q)$, Alice computes $r_{p}=y^{((p+1)/4)^{L}}~mod~p$ and $r_{q}=y^{((q+1)/4)^{L}}~mod~q$.
2. Compute the initial seed $x_{0}=(q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q})~{mod}~N$
3. From $x_{0}$, recompute the bit-vector ${\vec {b}}$ using the BBS generator, as in the encryption algorithm.
4. Compute the plaintext by XORing the keystream with the ciphertext: ${\vec {m}}={\vec {c}}\oplus {\vec {b}}$.

Alice recovers the plaintext $m=(m_{0},\dots ,m_{L-1})$.

Earl of Arundel (talk) 19:28, 25 June 2018 (UTC)

Thanks. In this context, for a prime number M, "$B^{-1}\mod M$" means "the (unique) integer x in the interval [1, M - 1] such that Bx is 1 more than a multiple of M." The whole expression you asked about is the product of this number with the number A. See Modular multiplicative inverse, although the context of that article is slightly more mathy and less CSy (so in particular there is a subtle difference in the formal meaning of the symbol "mod" at that article and in your quote). --JBL (talk) 20:24, 25 June 2018 (UTC)

Oh okay, well that makes sense. Thanks so much for the clarification. Cheers! Earl of Arundel (talk) 20:46, 25 June 2018 (UTC)