0

How to construct an integer $B$ that has the property of $B^2 \equiv N \pmod b$ and $B \equiv 0 \pmod c$, where $c$ belongs to a group of small prime numbers of the size $s$ and $b$ is a prime number outside that group.

I need to solve this in order to implement the polynomial selection part in the Self Initialized Quadratic Sieve algorithm.

So far I was able to compute a modular square root of $N \pmod b$ and find $B^2 \equiv N \pmod b$, but I don't know how to efficiently satisfy the second condition where $B \equiv 0 \pmod c$

Ilya Gazman
  • 1,440
  • So...in the end, you have $B\equiv n \pmod {p_1}$, where $n$ is a chosen square root of $N\pmod {p_1}$ and $B\equiv 0 \pmod {p_2}$ where $p_1,p_2$ are disjoint primes, yes? Seems like a standard Chinese Remainder Theorem calculation, or am I missing something? – lulu Aug 16 '20 at 20:24
  • Yes, the Chinese Remainder Theorem was mentioned in this context in an article I was reading about this. Can you please show me how to use it here? – Ilya Gazman Aug 16 '20 at 20:29
  • But this is a standard application...are you familiar with Chinese Remainder Theorem problems? – lulu Aug 16 '20 at 20:29
  • 1
    If $B\equiv 0 \pmod c$ then $B^2 \equiv 0\pmod c$. So you have $B^2 \equiv N \pmod b$ and $B^2 \equiv 0 \pmod c$. So use CRT – fleablood Aug 16 '20 at 20:31
  • @lulu No, I am not. I was reading the wiki article about it today, but I guess I need more. – Ilya Gazman Aug 16 '20 at 20:33
  • @fleablood can you please tell me what is CRT? – Ilya Gazman Aug 16 '20 at 20:33
  • CRT is a common abbreviation for the Chinese Remainder Theorem. – aras Aug 16 '20 at 20:34
  • CRT = Chinese Remainder Theorem. Read and reread the wiki article. That will tell you all you need. There isn't much more we can answer unless you have a specific question.. – fleablood Aug 16 '20 at 20:36
  • 1
    As others have commented, https://en.wikipedia.org/wiki/Chinese_remainder_theorem is the place to start. My advice is to create simple problems, such as $a \equiv 2\pmod{5}; a\equiv 3\pmod{7}$ and use this simple problem, along with the wikipedia article as practice. – user2661923 Aug 16 '20 at 20:51

1 Answers1

1

The comments have already told you that you need to use CRT (the Chinese Remainder Theorem), but it looks like you are asking for a bit more explanation as to how to use it.

Here's a first example: Say we want to find an integer $n$ which is $1$ mod $3$ and $3$ mod $5$. One way to list a bunch of $1$ mod $3$ numbers until we get a number that is $3$ mod $5$:

$$ 1, 4, 7, 10, \color{red}{13}, 16, 19, \dots $$

In this case $13$ is an answer.

We can also solve this problem the other way, by listing a bunch of $3$ mod $5$ numbers until we get a number that is $1$ mod $3$:

$$ 3, 8, \color{red}{13}, 18, \dots $$

Here's a second example: Now we want to find an integer $n$ which is $1$ mod $3$ and $3$ mod $6$. If we try to list a bunch of $1$ mod $3$ numbers, we never get a number which is $3$ mod $6$:

$$ 1, 4, 7, 10, 13, 16, 19, \dots \color{red}{??} $$

The reason why we can't find such an $n$ is because every number that is $3$ mod $6$ is divisible by $3$, and every number that is $1$ mod $6$ is not divisible by $3$. So the two conditions are incompatible.

By contrast, in the first example, the two conditions don't influence each other. In a certain way, "having a certain remainder mod $3$" has nothing to do with "having a certain remainder mod $5$", so you can always find such an $n$.

A more general way to write the first example is to say that we are looking for an $n$ which is a solution to the following system of equations:

\begin{align*} n &\equiv 1 \mod 3 \\ n &\equiv 3 \mod 5. \end{align*}

This is an instance of the following more general problem:

\begin{align*} n &\equiv a_1 \mod b_1 \\ n &\equiv a_2 \mod b_2. \end{align*}

In your case, $N = a_1$, $b = b_1$, $0 = a_2$, and $c = b_2$.

You've written that $b$ and $c$ are two different prime numbers. This means, just like the example with mod $3$ and mod $5$, that this system has a solution.

To find this solution, one simple computational method is to use the counting up method demonstrated above. For example, you could count up

$$ N, N + b, N + 2b, N + 3b, \dots $$

and keep going until you get a number which is $0$ mod $c$.

Then you will have some number $B^2$ for which $B^2 \equiv N \mod b$ and $B^2 \equiv 0 \mod c$. It seems like you've said you know how to find $B$ from here, so this should do the trick.

There are more efficient ways to solve this system of equations. As commenters have pointed out, Wikipedia has more information. Hopefully this is a good starting point to gain intuition. (Admittedly, the Wikipedia article looks slightly tricky for a beginner to learn from.) CRT is also a common topic in introductory number theory courses—you might also try googling around a bit and seeing how other people explain it.

aras
  • 5,649
  • I read the wiki and did some googling and now I understand how to efficiently solve your first example. But I still don't understand how to satisfy both of the conditions. I can compute $B$ such that $B^2\equiv N \pmod{b}$, and I can find $X$ such that $X\equiv 0 \pmod c$ and $X\equiv N \pmod b$ but I don't know how to use CRT to work with squares – Ilya Gazman Aug 16 '20 at 21:13
  • You want to solve the system of equations $x \equiv N \mod b$ and $x \equiv 0 \mod c$. Once you have this $x$, then you can set $B^2 = x$. Then, you say you know how to compute $B$ from here, since you know $B^2 \equiv x \equiv N \mod b$. – aras Aug 16 '20 at 21:25
  • I can't set $B^2=x$ since I need to make sure that $B$ is an integer, or maybe I didn't understand what you said... Sorry. – Ilya Gazman Aug 16 '20 at 23:46
  • Nvm, I think I figured it out. I first need to find $B$ such that $B^2\equiv N\pmod{b}$ and then find $x$ such that $x\equiv B \pmod b$ and $x\equiv 0 \pmod c$ – Ilya Gazman Aug 16 '20 at 23:55