TransWikia.com

Compositeness testing using Jacobi polynomials

Mathematics Asked by Peđa Terzić on July 30, 2020

Can you prove or disprove the following claim:

Let $P_n^{(alpha,beta)}(x)$ be Jacobi polynomial . If $p$ is a prime number such that $alpha , beta$ are natural numbers and $alpha + beta <p$, then $$P_p^{(alpha,beta)}(a) equiv a pmod{p}$$ for all odd integers $a$ greater than one .

You can run this test here. I have tested this claim for many random values of $p$ , $alpha$ and $beta$ and there were no counterexamples .

One Answer

We use the identity $$P_n^{(alpha,beta)}(x)=sum_{s=0}^n binom{n+alpha}{n-s}binom{n+beta}{s}left(frac{x-1}2right)^sleft(frac{x+1}2right)^{n-s},$$ and assume that $pgeq 3$. For $s=0$, the sum is simply $(x+1)/2$ modulo $p$ (by Fermat's little theorem), and for $s=p$, the sum is $(x-1)/2$, so those two terms sum to $x$. It suffices to show that $$sum_{s=1}^{p-1} binom{p+alpha}{p-s}binom{p+beta}{s}left(frac{x-1}2right)^sleft(frac{x+1}2right)^{p-s}equiv 0bmod p$$ for all integer $x$. We claim, in fact, that each of these terms are multiples of $p$. By Lucas's theorem, for $0<s<p$, $$binom{p+alpha}{p-s}equiv binom{1}{0}binom{alpha}{p-s}bmod p,$$ and $$binom{p+beta}{s}equiv binom{1}{0}binom{beta}{s}bmod p.$$ However, since $alpha+beta<s+(p-s)$, either $alpha<p-s$ or $beta<s$, so one of these is $0bmod p$.

Answered by Carl Schildkraut on July 30, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP