# Tag Info

4

If you know the prime factorization of $n=p_1 ^{d_1} \dots p_N ^{d_N}$, then the question has already been asked and answered: the number you are looking for is $\prod \limits _{k=1} ^N \gcd (n-1, p_k -1)$. If you do not know the factorization of $n$, then Pomerance has obtained a lower bound given by $\exp (\log x) ^{\frac E {E+1} - \varepsilon}$ (see ...

3

We have the following closed form for your sum. It requires knowing the prime factorisation of $n$, so it may not be useful for large $n$: If $n=\prod_rp_r^{k_r}$, then $$\sum_{k\leq n}\frac n{\gcd(n,k)}=\prod_r\frac{p_r^{2k_r+1}+1}{p_r+1}.$$ Proof. Each summand $\frac nd$ occurs as many times as there are $k\leq n$ s.t. $\gcd(k,n)=d$, that is, ...

1

Note that $|\mathbb{Z}_p^*| = 2^k$, so that every element has order a power of $2$. Now, if $a$ and $b$ are non-generators, then $|a| = 2^r$ and $|b|=2^s$ for $r, s < k$. But then $|ab| \le \textrm{lcm}(2^r, 2^s) = 2^{\max(r, s)} < 2^k$, so that $ab$ is also a non-generator. (Also, it's clear that $|a| = |a^{-1}|$, so the set of non-generators is also ...

1

Hint: Consider the contrapositive: $x^3 − a$ is reducible over $F_q$ if and only if $3\not\mid (q−1)$ or $3\mid(q−1)/ord(a)$. Note that $x^3 − a$ is reducible over $F_q$ iff it has a root in $F_q$.

1

In section 2, the paper gives this definition:

1

The RSA system (the textbook one, that sends $M$ to $M^e \mod N$) is bijective on the all $M$ with $\gcd(M,N) = 1$ or we could not decrypt. And we even know its inverse: $x \rightarrow x^d \mod N$. So it's a bijective map on $\{0,\ldots,N-1\}$, indeed. So not all $M$ in $\{0,\ldots,N-1\}$ can be messages, only those with no divisor with $N$ in common (so no ...

1

Hint: Use the extended Euclidean algorithm for $\gcd(x^6 + x^4 + x^3,x^8 + x^4 + x^3 + x + 1)$ and express $1=(x^6 + x^4 + x^3)p(x)+(x^8 + x^4 + x^3 + x + 1)q(x)$. Then you can interpret $p(x)$ as the desired inverse.

1

The number of points is $1+\sum_{x\in \mathbb F_p}\left(\left(\frac{x^3+ax+b}{p}\right)+1\right)$, where $\left(\frac{x^3+ax+b}{p}\right)$ is the Legendre symbol modulo $p$. If $x$ is not a root of $x^3+ax+b$, the term inside the sum is either $0$ or $2$. Otherwise, it is $1$. If $x^3+ax+b$ has a root, then it has either $1$ or $3$ roots and the sum is odd, ...

1

I think a third heuristic could be using the trigram frequency and the most frequent trigram is "the". The good thing about this trigram is that it covers both the most frequent letter and bigram in English language.

1

Regarding 1 or 3: E.g. Homomorphic encryption has been mentioned as "Holy grail of Cryptography". It would allow to provide encrypted inputs to some service provider, who would be able to perform useful calculations on the inputs, without him knowing the decrypted form. Kind of putting some ingredients into a locked box, giving it to the provider who ...

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