Wikipedia:Reference desk/Archives/Mathematics/2018 July 15

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

July 15

"Probable primes" that aren't, and cryptography

How bad is the impact on the strength of a cipher that requires a prime number, if instead one uses a probable prime that turns out to be composite? How does it change if the adversary knows that this has happened? Do the pseudoprimes tend to still have strength proportional to the length of the smallest prime factor? What are the distributions of factors for pseudoprimes that pass commonly-used probable-prime tests? NeonMerlin 00:24, 15 July 2018 (UTC)

Face it, if you have a factoring or discrete log problem instance, you might make a random guess at the answer and get it right on the first try. Getting a pseudoprime from a probabilistic test on numbers the size used in cryptography is extremely unlikely in about the same way. But, for example, if the pseudoprime had small factors, that could lead to a small-subgroup attack on a DL-based system, or easy factorization of an RSA modulus. If it had large factors then for factoring and DL I think there are some theorems that you're not that much worse off. E.g. there were some suggestions of using RSA moduli with 3 factors so you could decrypt faster using the CRT optimization. I don't know if there's a practical way to detect whether an RSA modulus has 2 factors or 3. For a DL modulus there are deterministic primality tests and also probabilistic tests (like the original Solovay-Strassen test) with guaranteed convergence (no anomalies like Carmichael numbers). 173.228.123.166 (talk) 08:10, 15 July 2018 (UTC)

As a practical matter, primality tests can find numbers whose probability of being composite is less than any given value, small enough for example that you could output one per second for the current age of the universe and not expect a composite to appear. Compared to that, I'd say that the chances of the encryption breaking because of a false pseudoprime are much less than the chances that someone will find a fast factoring algorithm or another way of breaking RSA in general. --RDBury (talk) 01:14, 16 July 2018 (UTC)

If $f(x)=\sum _{n=0}^{\infty }(-1)^{n}a_{n}x^{n}$ , then $\int _{0}^{\infty }{\frac {f(x)}{1+x}}dx=-\sum _{n=0}^{\infty }a'_{n}$

I've found using heuristic methods:

$\int _{0}^{\infty }{\frac {f(x)}{1+x}}dx=-\sum _{n=0}^{\infty }a'_{n}$

if

$f(x)=\sum _{n=0}^{\infty }(-1)^{n}a_{n}x^{n}$

and

$a'_{n}\equiv {\dfrac {da_{n}}{dn}}$.

This seems to work, although the summation may sometimes need to be redefined as $g(-1)$, where

$g(z)=\sum _{n=0}^{\infty }(-1)^{n}a'_{n}z^{n}$

with this analytically continued such that $g(-1)$ is well defined.

The only exception seems to be cases where $f(x)$ has a pole on the unit circle, e.g. if $f(x)={\frac {1}{1+x}}$, but in that case using $f(x)={\frac {1}{a+x}}$ and taking the limit $a\to 1$ at the end of the calculations gives the correct result.

Is there a rigorous version of this statement with rigorous conditions for $f(x)$? Count Iblis (talk) 20:48, 15 July 2018 (UTC)

There might be something to this, but a'_n needs to be more carefully defined. For example if you take a(x) = sin πx then a_n = 0 but a'_n is (-1)ⁿπ. The value of the lhs is then 0 but the rhs is -π/2 with analytic continuation. --RDBury (talk) 01:44, 16 July 2018 (UTC)

Sorry if I'm missing some context here (or perhaps the point entirely)... but given that $f(x)$ only depends on $a(n)$ at integer arguments, can't I arbitrarily modify the gradients of $a(n)$ at the integers without changing $f(x)$? Then it seems the sum of the $a'(n)$ values is independent of the left-hand side integral, and the equality can't hold. What am I missing? 92.12.162.58 (talk) 20:21, 19 July 2018 (UTC)

I think the idea is that a(n) is meant to be an analytic function of n, e.g. a(n)=1/(n+1), and then the coefficients are the values of this function on the natural numbers. But even then you have a valid point since a(n) can be 0 for n∈N without a(x) being 0. Perhaps if a was restricted to being a rational function something like this might work. --RDBury (talk) 00:42, 20 July 2018 (UTC)

Yes, it can be verified to work for a wide range of functions by replacing factorials in $a_{n}$ by gamma functions. I guess that one may then construct a proof including statements on how to define the derivative of $a_{n}$, by considering a complete set of functions for which the statement is true, e.g. $\exp(-sx)$ for all s with $Re(s)>0$. Count Iblis (talk) 16:05, 20 July 2018 (UTC)