Your code looks ok, except that you need to allow 2*size - size + 1 =
size + 1 limbs for the quotient.
I can't check the result of your computation because you didn't say
what p is. But I very much doubt that mpn_tdiv_qr has a bug, so
perhaps something else has gone wrong when you checked the result.
You may also want to check that you actually have 2*size limbs in the
product. This is probably not important, but it might save time in the
computation if you specify the size exactly.
Bill.
On 4 February 2013 22:29, mgundes <mg...@hotmail.com> wrote:
>
> Hi, I have tried my function to test on 64 bits CPU and OS with my 1024
> bits numbers. I wanted to get (a_ * b) mod p_.
>
> I call my function as "ModularReductionABP(a_, b_, SIZE_16, p_);". I
> prefered to use "mpn_tdiv_qr" function to get mod as Bill suggested. Do I
> use mpn_tdiv_qr function correctly in order to calculate equation? You also
> can see the results I got. I checked in python and it seems wrong :) Any
> review will be appreciated. Thanks.
>
>
> mp_limb_t a_[16] = {
>
> 0x172AABC8172AABC7, 0x172AABCA172AABC9, 0x172AABCC172AABCB,
> 0x172AABCE172AABCD, \
>
> 0x172AABD0172AABCF, 0x172AABD2172AABD1, 0x172AABD4172AABD3,
> 0x172AABD6172AABD5, \
>
> 0x172AABD8172AABD7, 0x172AABDA172AABD9, 0x172AABDC172AABDB,
> 0x172AABDE172AABDD, \
>
> 0x172AABE0172AABDF, 0x172AABE2172AABE1, 0x172AABE4172AABE3,
> 0x172AABE6172AABE5
>
> };
>
>
> mp_limb_t b_[16] = {
>
> 0x263BBAC5263BBAC4, 0x263BBAC7263BBAC6, 0x263BBAC9263BBAC8,
> 0x263BBACB263BBACA, \
>
> 0x263BBACD263BBACC, 0x263BBACF263BBACE, 0x263BBAD1263BBAD0,
> 0x263BBAD3263BBAD2, \
>
> 0x263BBAD5263BBAD4, 0x263BBAD7263BBAD6, 0x263BBAD9263BBAD8,
> 0x263BBADB263BBADA, \
>
> 0x263BBADD263BBADC, 0x263BBADF263BBADE, 0x263BBAE1263BBAE0,
> 0x263BBAE3263BBAE2
>
> };
>
>
> mp_limb_t p_[16] = {
>
> 0xFFFCCDC8FFFCCDC7, 0xFFFCCDCAFFFCCDC9, 0xFFFCCDCCFFFCCDCB,
> 0xFFFCCDCEFFFCCDCD, \
>
> 0xFFFCCDD0FFFCCDCF, 0xFFFCCDD2FFFCCDD1, 0xFFFCCDD4FFFCCDD3,
> 0xFFFCCDD6FFFCCDD5, \
>
> 0xFFFCCDD8FFFCCDD7, 0xFFFCCDDAFFFCCDD9, 0xFFFCCDDCFFFCCDDB,
> 0xFFFCCDDEFFFCCDDD, \
>
> 0xFFFCCDE0FFFCCDDF, 0xFFFCCDE2FFFCCDE1, 0xFFFCCDE4FFFCCDE3,
> 0xFFFCCDE6FFFCCDE5
>
> };
>
>
> /*
>
> (a * b) mod p
>
> */
>
> void ModularReductionABP(mp_limb_t *a, mp_limb_t *b, mp_size_t size,
> mp_limb_t *mod)
>
> {
>
> mp_limb_t multiplicationResult[size*2];
>
> memset(multiplicationResult, 0, size*2 * sizeof(mp_limb_t));
>
>
> gmp_printf("multiply..\n");
>
> mpn_mul(multiplicationResult,
>
> a, size,
>
> b, size);
>
>
> gmp_printf("result1: %Nu\n", multiplicationResult, size);
>
>
> mp_limb_t c[size];
>
> mp_limb_t d[size];
>
> memset(c, 0, size * sizeof(mp_limb_t));
>
> memset(d, 0, size * sizeof(mp_limb_t));
>
>
> mpn_tdiv_qr(c,d,0, multiplicationResult, 2*size, mod, size);
>
>
> gmp_printf("\nresult2: %Nu\n\n\n", c, size);
>
> gmp_printf("\nresult3: %Nu\n\n\n", d, size);
>
> }
>
>
> kays@vaio64 ~/bitbucket/directclass1 $ ./directclass
> multiply..
> result1:
> 31281781659108383759180173958845112706426388361681641530245996098380308639750083352747732789827718498185054130827808940526536050680884926042209184887699334785206221487960805670752790468657177265817154198670207174990288213545137774992462228884802070093390645505861602741915290739896925800431411039961739631196
>
> result2:
> 2429756350689766842694556740638161392277857848926668771080399749522920535325879270426445494248468898753801674387648617800632488461559493081196952232954152384865660243312530684478669749481313879910421763146520460034374221906008666223048145368346070028782670880568536251388917403070056424840082484158524859379
>
>
> result3:
> 119827277741323452445682903729823582048706420516522175626015394884400805867627030482198093601765997029383775676902120915520776000173466686652429756142248391127436426886472063872387092222440604402544020609660542632564066945743318810459630408032366484113006969187829316848492073764841523026162907833940468437367
>
>
>
> On Mon, Feb 4, 2013 at 10:39 AM, mgundes <mg...@hotmail.com> wrote:
>>
>>
>> Hi Case and Bill,
>>
>> Thanks for your answers, appreciated. I will try your suggestions in
>> the evening when I arrive home.
>>
>> Regards,
>> Thanks
>>
>>
>> On Sun, Feb 3, 2013 at 11:54 PM, Bill Hart <goodwillh...@googlemail.com>
>> wrote:
>>>
>>> Hi Mahmut,
>>>
>>> there is the division with remainder function (mpn_tdiv_qr). The
>>> remainder is the same thing as mod of course.
>>>
>>> In practice it takes about the same time to compute quotient and
>>> remainder as it does to compute just remainder.
>>>
>>> Bill.
>>>
>>> On 3 February 2013 20:48, mgundes <mg...@hotmail.com> wrote:
>>> >
>>> > Hi everybody,
>>> >
>>> > I need a function to do modular operation on big numbers. I
>>> > found
>>> > mpn_mod_1() but its modulus parameter are single mp_limb_t. I want to
>>> > use
>>> > also big modulus parameter, Is there any function mpn_mod() something
>>> > like
>>> > below to be able to give size of modulus?
>>> >
>>> > mp_limb_t mpn_mod (mp_limb_t *s1p, mp_size_t s1n,
>>> > mp_limb_t
>>> > *s2p, mp_size_t s2n)
>>> >
>>> > Thanks for your suggestions.
>>> >
>>> > Regards,
>>> > Thanks
>>> >
>>> > --
>>> > MahmutG
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> > Groups
>>> > "mpir-devel" group.
>>> > To unsubscribe from this group and stop receiving emails from it, send
>>> > an
>>> > email to mpir-devel+unsubscr...@googlegroups.com.
>>> > To post to this group, send email to mpir-devel@googlegroups.com.
>>> > Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
>>> > For more options, visit https://groups.google.com/groups/opt_out.
>>> >
>>> >
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "mpir-devel" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an
>>> email to mpir-devel+unsubscr...@googlegroups.com.
>>> To post to this group, send email to mpir-devel@googlegroups.com.
>>> Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>
>>
>>
>> --
>> MahmutG
>
>
>
>
> --
> MahmutG
>
> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to mpir-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to mpir-devel@googlegroups.com.
> Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to mpir-devel+unsubscr...@googlegroups.com.
To post to this group, send email to mpir-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/mpir-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
