umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff

umul(p1,p2)

umul_ff(p1,p2)

:: °ìÊÑ¿ô¿¹à¼°¤Î¹â®¾è»»

usquare(p1)

usquare_ff(p1)

:: °ìÊÑ¿ô¿¹à¼°¤Î¹â® 2 ¾è»»

utmul(p1,p2,d)

utmul_ff(p1,p2,d)

:: °ìÊÑ¿ô¿¹à¼°¤Î¹â®¾è»» (ÂǤÁÀڤ꼡¿ô»ØÄê)

return

°ìÊÑ¿ô¿¹à¼°

p1 p2

°ìÊÑ¿ô¿¹à¼°

d

ÈóÉéÀ°¿ô

• °ìÊÑ¿ô¿¹à¼°¤Î¾è»»¤ò, ¼¡¿ô¤Ë±þ¤¸¤Æ·è¤Þ¤ë¥¢¥ë¥´¥ê¥º¥à¤òÍѤ¤¤Æ ¹â®¤Ë¹Ô¤¦.
• umul(), usquare(), utmul() ¤Ï ·¸¿ô¤òÀ°¿ô¤È¸«¤Ê¤·¤Æ, À°¿ô·¸¿ô¤Î¿¹à¼°¤È¤·¤ÆÀѤòµá¤á¤ë. ·¸¿ô¤¬Í­¸ÂÂÎ GF(p) ¤Î¸µ¤Î¾ì¹ç¤Ë¤Ï, ·¸¿ô¤Ï 0 °Ê¾å p ̤Ëþ¤ÎÀ°¿ô¤È¸«¤Ê¤µ¤ì¤ë.
• umul_ff(), usquare_ff(), utmul_ff() ¤Ï, ·¸¿ô¤òÍ­¸ÂÂΤθµ¤È¸«¤Ê¤·¤Æ, Í­¸ÂÂξå¤Î¿¹à¼°¤È¤·¤Æ ÀѤòµá¤á¤ë. ¤¿¤À¤·, °ú¿ô¤Î·¸¿ô¤¬À°¿ô¤Î¾ì¹ç, À°¿ô·¸¿ô¤Î¿¹à¼°¤òÊÖ¤¹¾ì¹ç¤â¤¢¤ë¤Î¤Ç, ¤³¤ì¤é¤ò¸Æ¤Ó½Ð¤·¤¿·ë²Ì ¤¬Í­¸ÂÂη¸¿ô¤Ç¤¢¤ë¤³¤È¤òÊݾڤ¹¤ë¤¿¤á¤Ë¤Ï ¤¢¤é¤«¤¸¤á simp_ff() ¤Ç·¸¿ô¤òÍ­¸ÂÂΤ赤ËÊÑ´¹¤·¤Æ¤ª¤¯¤È¤è¤¤.
• umul_ff(), usquare_ff(), utmul_ff() ¤Ï, GF(2^n) ·¸¿ô¤Î¿¹à¼°¤ò°ú¿ô¤Ë¼è¤ì¤Ê¤¤.
• umul(), umul_ff() ¤Î·ë²Ì¤Ï p1, p2 ¤ÎÀÑ, usquare(), usquare_ff() ¤Î·ë²Ì¤Ï p1 ¤Î 2 ¾è, utmul(), utmul_ff() ¤Î·ë²Ì¤Ï p1, p2 ¤ÎÀÑ ¤Î, d ¼¡°Ê²¼¤ÎÉôʬ¤È¤Ê¤ë.
• ¤¤¤º¤ì¤â, set_upkara() (utmul, utmul_ff ¤Ë¤Ä¤¤¤Æ¤Ï set_uptkara()) ¤ÇÊÖ¤µ¤ì¤ëÃͰʲ¼¤Î¼¡¿ô¤ËÂФ·¤Æ¤ÏÄ̾ï¤ÎÉ®»» ·Á¼°¤ÎÊýË¡, set_upfft() ¤ÇÊÖ¤µ¤ì¤ëÃͰʲ¼¤Î¼¡¿ô¤ËÂФ·¤Æ¤Ï Karatsuba Ë¡, ¤½¤ì°Ê¾å¤Ç¤Ï FFT¤ª¤è¤ÓÃæ¹ñ¾ê;ÄêÍý¤¬ÍѤ¤¤é¤ì¤ë. ¤¹¤Ê¤ï¤Á, À°¿ô¤ËÂФ¹¤ë FFT ¤Ç¤Ï¤Ê¤¯, ½½Ê¬Â¿¤¯¤Î 1 ¥ï¡¼¥É°ÊÆâ¤ÎË¡ mi ¤òÍÑ°Õ¤·, p1, p2 ¤Î·¸¿ô¤ò mi ¤Ç³ä¤Ã¤¿Í¾¤ê¤È¤·¤¿¤â¤Î¤ÎÀѤò, FFT ¤Ç·×»»¤·, ºÇ¸å¤ËÃæ¹ñ¾ê;ÄêÍý¤Ç¹çÀ®¤¹¤ë. ¤½¤ÎºÝ, Í­¸ÂÂÎÈǤδؿô¤Ë ¤ª¤¤¤Æ¤Ï, ºÇ¸å¤Ë´ðÁÃÂΤòɽ¤¹Ë¡¤Ç³Æ·¸¿ô¤Î¾ê;¤ò·×»»¤¹¤ë¤¬, ¤³¤³¤Ç¤Ï Shoup ¤Ë¤è¤ë¥È¥ê¥Ã¥¯ [Shoup] ¤òÍѤ¤¤Æ¹â®²½¤·¤Æ¤¢¤ë.

[176] load("fff")$
[177] cputime(1)$
0sec(1.407e-05sec)
[178] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
0sec(0.00028sec)
[179] A=randpoly_ff(100,x)$
0sec(0.001422sec)
[180] B=randpoly_ff(100,x)$
0sec(0.00107sec)
[181] for(I=0;I<100;I++)A*B;
7.77sec + gc : 8.38sec(16.15sec)
[182] for(I=0;I<100;I++)umul(A,B);
2.24sec + gc : 1.52sec(3.767sec)
[183] for(I=0;I<100;I++)umul_ff(A,B);
1.42sec + gc : 0.24sec(1.653sec)
[184] for(I=0;I<100;I++)usquare_ff(A);  
1.08sec + gc : 0.21sec(1.297sec)
[185] for(I=0;I<100;I++)utmul_ff(A,B,100);
1.2sec + gc : 0.17sec(1.366sec)
[186] deg(utmul_ff(A,B,100),x);
100

»²¾È

section set_upkara, set_uptkara, set_upfft, section kmul, ksquare, ktmul.

Go to the first, previous, next, last section, table of contents.