modulus of data that is stored in an array

[amitk3553]

I had to take modulus of data that is stored in an array of 16 locations(32 bits stored on each location)

unsigned int arr_1 [16];

arr_1 % 2^256;//modulus 

 

how it would be possible?

[giblit]

If there are 16 numbers you are going to have to do it to each one?

const int size = 16;
for( int i = 0; i < size; ++i )
    arr_1[i] % 2^256;

Also if you are trying to do 2²⁵⁶ that is2 << 255 not [code] ^ is the XOR operator. If not ignore that comment.

*edit actually 2²⁵⁶ wouldn't make sense if they are 32 bit numbers.

[amitk3553]

Actually i had number of 512 bits and i have to calculate modulus of that with 2^256(2 raise power 256).

I had stored that no of 512 bits in an array of 16 locations.

So in this case how modulus calculation would be preformed?

[giblit]

Modulus operations are Number_base % base^x which is equal to the last x digits of Number_base


111 % 2 or 0110 1111₂ % 2¹ == last 1 digit == 1₂ == 1

111 % 4 or 0110 1111₂ % 2 ² == last 2 digits == 11₂ == 3

ect...

So for you it will be arr_1[511] -> arr_1[255]

[amitk3553]

like if it is
256 bits % (2 ^ 256)
the result is 0?

and
257 bits % (2 ^ 256)
the result is 257th bit?

[JLBorges]

> i had number of 512 bits and i have to calculate modulus of that with 2^256(2 raise power 256).
> I had stored that no of 512 bits in an array of 16 locations.

To get the mod result as an array, take the least significant 8 locations of the array.

To get the mod result as a number, use a large integer library.
Take the least significant 8 locations of the array and form the number by shifting and adding.

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <cstdint>
#include <algorithm>

int main()
{
    const std::size_t NBITS_ELEMENT = 32 ; // 32 bits in std::uint32_t
    const std::size_t NBITS_MODULUS = 256 ;

    static_assert( NBITS_MODULUS%NBITS_ELEMENT == 0, "integral multiple" ) ;
    // the elements to be considered are the ones that will
    // contribute to the least significant NBITS_MODULUS bits
    const std::size_t N = NBITS_MODULUS / NBITS_ELEMENT ;

    const std::size_t SZ = 16 ;
    std::uint32_t arr[SZ] ; // most significant 32 bits at arr[0]
    // fill array with values 10, 11, 12, ...
    std::iota( arr, arr+SZ, 10 ) ;

    for( std::uint32_t v : arr ) std::cout << v << ' ' ;
        std::cout << '\n' ;

    {
        std::uint32_t arr_mod_result[N] ;
        std::copy( arr+SZ-N, arr+SZ, arr_mod_result ) ;

        std::cout << "mod result (as array): " ;
        for( std::uint32_t v : arr_mod_result ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }

    {
        std::cout << "\n------------------\nmod result (as big number):\n" ;
        using boost::multiprecision::cpp_int ;

        cpp_int result ;
        for( std::size_t i = SZ-N ;  i < SZ ; ++i ) // pick up the last N values
        {
            const std::size_t shl = (SZ-i-1) * NBITS_ELEMENT ;
            std::cout << arr[i] << " << " << shl << " +\n" ;
            result += ( cpp_int(arr[i] ) << shl ) ; // shift and add
        }

        std::cout << "-----------\n== " << result << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/18bb3cbd42ee6fc6