<?xml version="1.0" encoding="iso-8859-1" ?>
<rss version="2.0">
  <channel>
    <title>2012 Reports</title>
    <link>http://eprint.iacr.org/forum/list.php?12</link>
    <description><![CDATA[Discussion forum for Cryptology ePrint Archive reports posted in 2012. Please put the report number in the subject.]]></description>
    <language>EN</language>
    <pubDate>Sat, 01 Sep 2012 15:25:25 -0600</pubDate>
    <lastBuildDate>Sat, 01 Sep 2012 15:25:25 -0600</lastBuildDate>
    <category>2012 Reports</category>
    <generator>Phorum 5.1.22</generator>
    <ttl>600</ttl>
    <item>
      <title>2012/470 primitive roots: well known, standard</title>
      <link>http://eprint.iacr.org/forum/read.php?12,881,881#msg-881</link>
      <author>djb</author>
      <description><![CDATA[Henri Cohen, &quot;A course in computational algebraic number theory&quot;, first edition, 1993, Algorithm 1.4.4, checks whether an integer modulo p is a primitive root by checking exponents (p-1)/p_1, (p-1)/p_2, ...; here p_1, p_2, ... are the distinct prime divisors of p-1.

The comments after the algorithm describe various speedups, including the following: &quot;The test for p_i=2 can be replaced by the more efficient check that the Legendre symbol ... is equal to -1 (see Algorithm 1.4.10 below).&quot;

eprint 2012/470 proposes &quot;an improvement of the classic randomized algorithm for generating primitive roots modulo a prime, by replacing an exponentiation with the evaluation of the Legendre-Jacobi symbol, which is much faster.&quot; This is exactly the same speedup.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago]]></description>
      <category>2012 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?12,881,881#msg-881</guid>
      <pubDate>Sat, 01 Sep 2012 15:25:25 -0600</pubDate>
    </item>
  </channel>
</rss>
