R devel - Jan 2006 - [R] Integer bit size and the modulus operator (PR#8541)

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.

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
>>>
>>> ______________________________________________
>>> R-help at stat.math.ethz.ch mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide! 
>>> http://www.R-project.org/posting-guide.html
>>
>>

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
>>>>
>>>> ______________________________________________
>>>> R-help at stat.math.ethz.ch mailing list
>>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>>> PLEASE do read the posting guide!
>>>> http://www.R-project.org/posting-guide.html
>>>
>>>
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>
>
-- 
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

On Mon, 30 Jan 2006, Prof Brian Ripley wrote:
> 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.
I think this one was a consequence of the other one.  I did get a valgrind 
error from there, but it looks as if copyMostAttrib does the necessary 
protection, if ans has not already been damaged.
> 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
>>>>> 
>>>>> ______________________________________________
>>>>> R-help at stat.math.ethz.ch mailing list
>>>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>>>> PLEASE do read the posting guide!
>>>>> http://www.R-project.org/posting-guide.html
>>>> 
>>>> 
>> 
>> ______________________________________________
>> R-devel at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-devel
>> 
>> 
>
> -- 
> 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
>
-- 
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