-1
$\begingroup$

I am reading this paper, but I will write everyting I need for my question here. So, long story short, we have a proth-number $n$, i.e. $n = h\cdot 2^k+1$ for odd $h<2^k$. We are looking for integers $D$ such that the Jacobi symbol $$ \left(\frac{D}{n}\right) \neq 1. $$ I could already prove that $$ \left(\frac{D}{n}\right) = \left(\frac{n}{D}\right),$$ so we can reduce $n \pmod D$. Now I know that $$ h\cdot 2^k+1 \equiv (h\pmod D)\cdot 2^{k\mod ord_p(2)}\pmod D,$$ where $ord_p(2)$ is the order of $2$ modulo $D$. So of course we are interested in finding a $D$ with a possibly low order, because if $D$ is a solution for a $k$, then it's a solution for every $k\pmod{ord_p(2)}$. What I do not understand is this: In (4.1) of the paper, they say: this here

But I do not get the link. Why is it useful to factorize $2^u-1$?

$\endgroup$
1
  • 1
    $\begingroup$ Please, use descriptive titles. "Problems understanding a paper" says nothing about the subject of the question. $\endgroup$
    – jjagmath
    Mar 8 at 14:23

1 Answer 1

Reset to default
1
$\begingroup$

Any prime $D$ that divides $2^u-1$ satisfies $2^u-1\equiv 0\pmod D$, which means that $2^u\equiv 1\pmod D$, i.e. $\mathrm{ord}_p(2)\mid u$.

$\endgroup$
3
  • $\begingroup$ I see, thank you. So, is this "just" a way to determine the order of 2 mod prime p? (The paper is from 1993) $\endgroup$
    – mathquester
    Mar 8 at 15:58
  • $\begingroup$ More precisely, it is a way to find all primes for which $2$ has order $u$, because for all prime factors of $2^u-1$ the multiplicative order of 2 is $u$ (or smaller), and any prime $D$ for which $2^u\equiv1\pmod D$ must be a factor of $2^u-1$. $\endgroup$
    – student91
    Mar 8 at 16:03
  • $\begingroup$ Do you maybe mean at most $u$? Because $2^{10}-1 = 3\cdot 11\cdot 31$ and the orders are $2,10,5$. $\endgroup$
    – mathquester
    Mar 8 at 16:14

You must log in to answer this question.

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