<p>It&#39;s all on these two functions. Three most frequently used operations of Num (ModP x) are (+) (-) (*),each of them will at least call p2num once(to get the modulus), in addition multiplication will call montgKeys. usual implementation do both in constant time: p2num is written as number literal with type &quot;Integral a=&gt;a&quot;, so a reasonable implementation should handle these two function in constant time(in amortized time, of course).</p>

<div class="gmail_quote">On Nov 7, 2011 2:27 PM, &quot;Ivan Lazar Miljenovic&quot; &lt;<a href="mailto:ivan.miljenovic@gmail.com">ivan.miljenovic@gmail.com</a>&gt; wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 7 November 2011 16:54, Bin Jin &lt;<a href="mailto:bjin1990@gmail.com">bjin1990@gmail.com</a>&gt; wrote:<br>
&gt; The actual time to calculate p2num and montgKeys are both O(log P). What I&#39;m<br>
&gt; looking is a constant time lookup.<br>
<br>
Are these two functions CPU bottlenecks as revealed by profiling?  If<br>
not, then you&#39;re probably over-optimising.<br>
<br>
Note that if O(1) lookup is really required, then that implies you use<br>
a static array, which requires you to pre-populate such an array with<br>
all possible values.<br>
<br>
--<br>
Ivan Lazar Miljenovic<br>
<a href="mailto:Ivan.Miljenovic@gmail.com">Ivan.Miljenovic@gmail.com</a><br>
<a href="http://IvanMiljenovic.wordpress.com" target="_blank">IvanMiljenovic.wordpress.com</a><br>
</blockquote></div>