# Tag Info

4

I wondered if there is a "simple" description of the set of numbers n that have this property. Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24. In other words, each prime must be a member of ...

0

The method you describe is called the "pencil and paper algorithm" and is well described in Knuth's Book, Semi-Numerical Algorithm II. In fact the number of steps can be easily determined by the size of operands. If Dividend D, is m-bit and Divisor d, is n-bit, then the Quotient q, will be (m-n+1)-bit, and the remainder in case of binary division will be at ...

2

Note that $f$ is irreducible over $\mathbb F_2$, which you can easily show using the observation that if it was reducible, there was a non-trivial divisor of degree $1$ or $2$, and disproving both of these possibilities by trial division. Therefore, $\mathbb Z_2[x]/(f)$ forms a field isomorphic to $\mathbb F_{2^{\deg f}}=\mathbb F_{16}$. Since the non-zero ...

0

Hint: modular inverses are unique, therefore the following holds: $$2^x \equiv 3 \pmod{p} ~ ~ \iff ~ ~ 2^{-x} \equiv 3^{-1} \pmod{p}$$ Now what is the inverse of $3$ modulo this particular $p$? Can you express it as a power of two modulo $p$? Solve for $x$. If you end up with a negative $x$, use Fermat's little theorem to derive a positive exponent.

0

My educated guess is that $z=x^3+ax+b$. After all, $y$ satisfies $y^2=z$. The reason as to why that formula works comes from Fermat's little theorem. If $u\not\equiv0\pmod p$, then we have $u^{p-1}\equiv1\pmod p$. Because we are working in $GF(p)$ where equality is defined via congruence modulo $p$ I keep it simpler and write this as $u^{p-1}=1$ for all ...

3

The equations mod 1 are supposed to have solutions that are very close to an integer value, say 3.99 or 4.01, which are reduced to a value very close to 0 (or 1, which is 0 mod 1). Specifically, they describe a set of samples that equate to the distance from an integer value all within $± {1/n}$ for some large value $n$, and the sum of the sample set is ...

3

You want to find a point $(X,Y)$ on an elliptic curve $y^2 = x^3 + ax + b$ knowing only $X$ and a single bit indicating whether $Y$ is even or odd. To find $Y$, you use the relation defining the curve: you know that $Y^2 = X^3 + aX + b$ since the point is on the curve. So you compute $X^3 + aX + b$ using your value of $X$ and the public parameters $a, b$, ...

Top 50 recent answers are included