Tag Info

Hot answers tagged

4

I suppose that $p$ is odd and that we start with a nonzero quadratic residue $x$. Proposition: If $p\equiv3\pmod{4}$, the iteration can run endlessly, or be terminated at any step, depending on which squareroot is chosen. If $p\equiv1\pmod{4}$ and the order $m$ of the starting square is even, then the squareroot iteration ends exactly after $t$ steps, ...


2

It takes my C+GMP code under 0.4s to do a BLS75 theorem 5 proof on the number, so this seems like the easiest option. This involves finding some small factors of p-1, checking conditions, then verifying primality of each factor (note you don't need to factor p-1 completely). This example has lots of small factors, and the large resulting prime minus 1 ...


2

Assuming we are additionally given that $0\le m<N$, then, yes, it is possible to reveal $m$: Just try the candidates one by one and check if $(m+r)^e\bmod B$ turns out to be $C$. Mathematically, this solves the problem. Also, we have found an explicit algorithm, albeit with exponential running time ($O(N)$, which is linear in $N$, but exponential in the ...


1

In Shannon Entropy, MUST the probability be based solely on the sequence itself or can the probabilities be predetermined Rather on the contrary (if I understand you right): the probabilities must be predetermined. More precisely: the Shannon entropy is defined in terms of a probabilistic model, it assumes that the probabilities are known. Hence, it ...


1

Taking up @ccorn's suggestion, here is my slighty expanded comment as an answer: With $p,q$ odd primes and $p\ne q$ the restrictions for the public RSA exponent $e$ is $1 < e < \varphi(pq)$ and $\gcd(e, \varphi(pq))=1.$ Because you have a more restrictive lower bound, your smallest exponent $e$ can be found as the smallest odd $e > 1000$ with ...


1

You have a finite field of order $p$, and it's multiplicative group is cyclic of order $p-1$. So there is a generator $\alpha$ for this multiplicative group, and any element of $\mathbb{F}_{p}^{*}$ can be written as $\alpha^{k}$. It is a quadratic residue iff $k$ is even, in which case it's square roots are $\pm \alpha^{k/2}$ (which can again be written as ...


1

Yes. A relation $\mathrel{R}$ is antisymmetric if $$x\mathrel{R}y\quad\text{and}\quad y\mathrel{R}x\quad\text{implies}\quad x=y\;.$$ This means that if $x\ne y$, you can’t have both $x\mathrel{R}y$ and $y\mathrel{R}x$: you can have at most one of them. It says nothing at all about what you can (or must) have when $x=y$. In terms of the associated graph, ...


1

Note that the first column of the resultant matrix is $[137,99]^T$. On the one hand $$\begin{bmatrix}6 & 25\\12 & 15\end{bmatrix} \begin{bmatrix}2 & b\\5 & d\end{bmatrix} = \begin{bmatrix}137 & 17\\99 & 22\end{bmatrix}$$ and on the other hand $$\begin{bmatrix}6 & 25\\12 & 15\end{bmatrix} \begin{bmatrix}2 & b\\5 & ...



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