// xcas version=0.7.3 fontsize=20 font=0
// fltk 7Fl_Tile 23 -480 920 507 20 0
[
// fltk N4xcas7EditeurE 23 -480 920 439 20 0
918 ,
// trouve p et q tel que le produit de 2 polynomes a coeff entiers
// de norme <= P et de somme des degres < n puisse se calculer
// dans Z/qZ avec une fft sur des poly de degre < p
cherche_p_q(n,P):={
  local p,q,t,j,k;
  p:=2^(ceil(log(n)/log(2))); // powerpc de 2 immediatement superieure a n
  q:=p*ceil(P*P*n/p); 
  // majoration sur les coeffs du polynome produit par un multiple de p
  // recherche d'un multiple de p plus grand ou egal tel que 
  // ce multiple + 1 soit premier
  for (t:=q/p;;q+=p,t++){
    if (isprime(q+1))
      break;
  }
  q++;
  // recherche d'une racine p-ieme de 1 dans Z/qZ (ou q=p*t+1 et ou q premier)
  // on sait que j^(q-1)==j mod q, on essaie j^t (doit etre != 1 et ^(p/2)!=1)
  for (j:=1;;j++){
    if ( (k:=powmod(j,t,q))!=1 ){
      if (powmod(k,p/2,q)!=1){
        break;
      }
    }
  }
  print("somme des degres<",p,"Z/qZ=",q,"racine p-ieme de 1",k);
  return p,q,k;
}:;,
// fltk N4xcas10Log_OutputE 23 -41 920 45 20 0
// Parsing cherche_p_q£// Success compiling cherche_p_q£
,
// fltk N4xcas8EquationE 23 4 920 23 20 0
"Done"
]
,
// fltk 7Fl_Tile 23 29 920 24 20 0
[
// fltk N4xcas23Comment_Multiline_InputE 23 29 920 24 20 0
On veut multiplier des polynomes dont la somme des degres est < 124 et de coeff max < 17
,
// fltk N4xcas10Log_OutputE 23 53 920 4 20 0

]
,
// fltk 7Fl_Tile 23 55 920 75 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 55 920 28 20 0
cherche_p_q(124,17)
,
// fltk N4xcas10Log_OutputE 23 83 920 24 20 0
"somme des degres<",128,"Z/qZ=",35969,"racine p-ieme de 1",22798£
,
// fltk N4xcas8EquationE 23 107 920 23 20 0
128,35969,22798
]
,
// fltk 7Fl_Tile 23 132 920 24 20 0
[
// fltk N4xcas23Comment_Multiline_InputE 23 132 920 24 20 0
on verifie que 22798 est une racine primitive d'ordre 128 de 1
,
// fltk N4xcas10Log_OutputE 23 156 920 4 20 0

]
,
// fltk 7Fl_Tile 23 158 920 47 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 158 920 27 20 0
powmod(22798,128,35969)
,
// fltk N4xcas10Log_OutputE 23 185 920 1 20 0

,
// fltk N4xcas8EquationE 23 186 920 23 20 0
1
]
,
// fltk 7Fl_Tile 23 207 920 47 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 207 920 27 20 0
powmod(22798,64,35969)
,
// fltk N4xcas10Log_OutputE 23 234 920 1 20 0

,
// fltk N4xcas8EquationE 23 235 920 23 20 0
35968
]
,
// fltk 7Fl_Tile 23 256 920 31 20 0
[
// fltk N4xcas23Comment_Multiline_InputE 23 256 920 30 20 0
Creation d'un poly de degre 60 a coeff aleatoires dans 0..9 et completion par 68 zeros -> 128 coeffs
,
// fltk N4xcas10Log_OutputE 23 286 920 1 20 0

]
,
// fltk 7Fl_Tile 23 289 920 74 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 289 920 30 20 0
P:=poly1[op(ranm(1,60,10)[0]),0$68]
,
// fltk N4xcas10Log_OutputE 23 319 920 1 20 0

,
// fltk N4xcas8EquationE 23 320 920 43 20 0
poly1[2,3,5,6,4,1,5,4,6,4,7,8,0,9,3,7,4,8,9,4,3,6,6,3,3,0,6,4,2,6,2,6,9,7,2,4,7,0,4,9,0,4,1,3,9,7,5,8,8,6,4,7,0,7,2,2,7,3,6,7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]
,
// fltk 7Fl_Tile 23 365 920 71 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 365 920 27 20 0
p:=fft(P,22798,35969)
,
// fltk N4xcas10Log_OutputE 23 392 920 1 20 0

,
// fltk N4xcas8EquationE 23 393 920 43 20 0
[284,-109,4480,13514,9754,-16974,-5939,6443,-9565,-12961,-11993,-13725,15323,-4516,7310,13260,13375,-1109,17264,-12832,4051,-15251,14518,-9270,-10727,-10779,5762,-8270,-14987,-5325,17942,8562,4396,-162,-13010,-8873,13915,1806,-3713,16481,12311,-7315,14125,17039,-4883,-16876,-1475,-13408,-13976,-14747,-12167,13467,75,-5244,-6670,750,11251,-6930,-7618,15286,18,15216,-12332,11440,-22,-1257,7956,-10017,7016,8375,-14580,8450,-14468,6477,9668,6213,-16185,-11469,2431,6390,-10665,644,-7459,-14196,13309,10890,-15644,8746,-16106,17136,8845,8965,-12960,-8824,1020,15621,-4402,-6248,10649,-8687,-6441,-165,11930,3708,10221,11480,-16328,7882,4882,4678,7206,-14124,11322,-9112,13093,9212,10349,7499,7815,3957,17139,-3834,8755,-16344,12717,2405,-6096,7089]
]
,
// fltk 7Fl_Tile 23 438 920 70 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 438 920 30 20 0
Q:=ifft(p .* p,22798,35969)
,
// fltk N4xcas10Log_OutputE 23 468 920 1 20 0

,
// fltk N4xcas8EquationE 23 469 920 43 20 0
[4,12,29,54,77,88,102,104,126,160,201,228,247,284,302,302,350,418,414,502,483,576,494,540,638,560,633,558,687,642,657,670,742,736,772,840,791,820,740,928,859,826,946,842,908,920,1011,1080,1037,1208,1188,1124,1182,1172,1292,1200,1206,1302,1268,1338,1314,1366,1434,1218,1333,1334,1337,1236,1220,1132,1098,1126,1031,936,1036,998,960,1082,851,872,1006,714,818,802,705,762,705,686,699,738,683,668,767,508,630,648,462,592,522,390,472,422,459,464,456,342,377,334,206,246,172,124,183,94,121,134,78,84,49,0,0,0,0,0,0,0,0,0]
]
,
// fltk 7Fl_Tile 23 510 920 76 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 510 920 32 20 0
P2:=P*P
,
// fltk N4xcas10Log_OutputE 23 542 920 1 20 0

,
// fltk N4xcas8EquationE 23 543 920 43 20 0
poly1[4,12,29,54,77,88,102,104,126,160,201,228,247,284,302,302,350,418,414,502,483,576,494,540,638,560,633,558,687,642,657,670,742,736,772,840,791,820,740,928,859,826,946,842,908,920,1011,1080,1037,1208,1188,1124,1182,1172,1292,1200,1206,1302,1268,1338,1314,1366,1434,1218,1333,1334,1337,1236,1220,1132,1098,1126,1031,936,1036,998,960,1082,851,872,1006,714,818,802,705,762,705,686,699,738,683,668,767,508,630,648,462,592,522,390,472,422,459,464,456,342,377,334,206,246,172,124,183,94,121,134,78,84,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]
,
// fltk 7Fl_Tile 23 588 920 74 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 588 920 30 20 0
revlist(P2)-revlist(Q)
,
// fltk N4xcas10Log_OutputE 23 618 920 1 20 0

,
// fltk N4xcas8EquationE 23 619 920 43 20 0
poly1[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]
,
// fltk 7Fl_Tile 23 664 920 31 20 0
[
// fltk N4xcas19Multiline_Input_tabE 23 664 920 30 20 0

,
// fltk N4xcas10Log_OutputE 23 694 920 1 20 0

]