Integer bit size and the modulus operator (PR#8541)

On Mon, 30 Jan 2006 murdoch at stats.uwo.ca wrote:

On 1/30/2006 1:39 PM, Ionut Florescu wrote:

Thank you for the quick reply, I will look into the R packages.
For crashing R try this:

generator.zp=function(x,p)
{a=1:(p-1); b=x^a%%p;
if(all(b[1:(p-2)]!=1)&&(b[p-1]==1)){return(x, " Good ")}
else{return(x, " No Good, try another integer ")}
}

Thanks, I can reproduce the crash using

for (x in 10:100) generator.zp(x, 41)

I'll see if I can track down what's going wrong.  By the way, you're not
supposed to use two arguments to return():  that's not supposed to be
allowed any more.  I'm somewhat surprised you don't get an error from
it.  But that's not the cause of the crash.

You do get a warning, though.  It *is* allowed, see ?return.

One error is the following in real_binary:

   if (n1 > n2)
	copyMostAttrib(s1, ans);
   else if (n1 == n2) {
	copyMostAttrib(s2, ans);
	copyMostAttrib(s1, ans);
   }
   else
	copyMostAttrib(s2, ans);

Here ans is not PROTECTED.

The second is in the warning, which causes allocation when ans is not 
protected.

Fixed in R-devel and 2.2.1 patched.

Duncan Murdoch

This checks if element x is a generator of the group Z_p. If you try
this function for p = 41 and x various increasing values eventually it
will crash R. That is what I meant by random, at first I started x=2,3
so on, when I got to 8, R crashed. Now apparently I can get to 15. When
I tried again I got to 20.

Ionut Florescu


Duncan Murdoch wrote:

On 1/30/2006 11:32 AM, Ionut Florescu wrote:

I am a statistician and I come up to an interesting problem in
cryptography. I would like to use R since there are some statistical
procedures that I need to use.
However, I run into a problem when using the modulus operator %%.

I am using R 2.2.1 and when I calculate modulus for large numbers
(that I need with my problem) R gives me warnings. For instance if
one does:
a=1:40;
8^a %% 41
one obtains zeros which is not possible since 8 to any power is not a
multiple of 41.
In addition when working with numbers larger that this and with the
mod operator R crashes randomly.

Could you keep a record of the random crashes, and see if you can make
any of them repeatable?  R shouldn't crash.  If you can find a
repeatable way to make it crash, then that's a bug that needs to be
fixed.  (If it crashes at random it should still be fixed, but it's so
much harder to fix that it's unlikely to happen unless the cases are
ones that look likely to come up in normal situations.)

I believe this is because R stores large integers as real numbers
thus there may be lack of accuracy when applying the modulus operator
and converting back to integers.

So my question is this: Is it possible to increase the size of memory
used for storing integers? Say from 32 bits to 512 bits (Typical size
of integers in cryptography).

No, but there is at least one contributed package that does multiple
precision integer arithmetic.  I can't remember the name of it right
now, but Google should be able to find it for you...

Duncan Murdoch

Thank you, any help would be greatly appreciated.
Ionut Florescu

-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595