1
$\begingroup$

Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.

Given an interval $[a,b]$ what is the best way to test given integer $q$ has no composite factor allowed in $[a,b]$? Can any non-trivial primality test be specialized?

Improve this question
$\endgroup$
4
  • $\begingroup$ If a+2 is less than b+2 is less than a+a, start with gcd(q,c) where c = b choose a-1. Otherwise split the interval up. Gerhard "Best Way Known To Me" Paseman, 2017.11.04. $\endgroup$
    – Gerhard Paseman
    Commented Nov 4, 2017 at 21:53
  • $\begingroup$ $c=\binom{b}{a-1}$ could be large (say $a=5\times 10^{100}, b=6\times 10^{100}$ (also I do not get why use $gcd(q,c)$))? $\endgroup$
    – Turbo
    Commented Nov 4, 2017 at 21:56
  • $\begingroup$ @Turbo The very first step of the euclidean algorithm is replacing c with c modulo q. So you can just compute the binomial coefficient modulo q in the first place to avoid that particular problem. $\endgroup$
    – Johannes Hahn
    Commented Nov 4, 2017 at 22:21
  • $\begingroup$ @JohannesHahn 1. I would not know how to compute binomial coefficients mod $q$ in poly time. 2. I do not know why this is useful at all. $\endgroup$
    – Turbo
    Commented Nov 4, 2017 at 22:24

1 Answer 1

Reset to default
5
$\begingroup$

Checking whether an integer $n$ has a divisor in a given interval is essentially equivalent to factorization. Factoring is essentially equivalent to finding the smallest prime factor. So suppose that $n$ is not prime. Then check whether $n$ has a prime factor in $[1, n^{1/4}]$. Depending on the outcome check whether $n$ has a factor in $[1, n^{1/8}]$ or in $[n^{1/4}, n^{3/8}]$. After $\frac{\log n}{\log 2}$ steps you have determined the smallest prime factor of $n$. So as far as we know, checking for factors in an arbitrary interval is a lot more difficult than checking for factors in $[2, n-1]$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ "Checking whether an integer $n$ has a divisor in a given interval is essentially equivalent to factorization" no it is not. $\endgroup$
    – Turbo
    Commented Nov 5, 2017 at 8:54
  • 1
    $\begingroup$ @Turbo And what is unclear to you in Jan-Christoph's proof that indeed it is? $\endgroup$
    – Johannes Hahn
    Commented Nov 5, 2017 at 13:45
  • $\begingroup$ how is it equivalent to factoring? it is harder than factoring. He gives one reduction. He reduces factoring to finding no factors in an interval. He only proves the new problem is at least as hard as factoring which is implicit in the question as I may have very well given $q$ along all its prime factors and the difficulty morally remains similar. $\endgroup$
    – Turbo
    Commented Nov 5, 2017 at 19:32
  • $\begingroup$ Is the factor $\log n$ bothering you? $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Nov 6, 2017 at 18:05
  • $\begingroup$ @Jan-ChristophSchlage-Puchta your answer does not relate to the problem. $\endgroup$
    – Turbo
    Commented Nov 7, 2017 at 22:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .