In Miller-Rabin Primality Test for $n$ we first represent $n-1$ as $u\times2^k$ and then random choose some $a$ from the set $\{2 ,3 \cdots n-2\}$ and then we compute $b_0(=a^u),b_1(=b_0^2)\cdots b_{k-1},b_k$ (all computations are modulo $n$) and then test for various conditions.
My question is - rather than randomly choosing $a$ cant we choose such $a$ whose probability of being a A-Witness is higher.
Since $W_n^F \subset W_n^A$ i.e. every Fermat Witness is a A-Witness and $\mathbb{Z}_n^*-(\mathbb{Z}_n-\{0\})$ contains Fermat's Witness. So if we choose $a$ from this set, isn't the algorithm will be faster in case $n$ is composite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.