/* bc program padic */
/* 16th March 2011  */
/* p an odd prime, not dividing a.
 * a[0]^2=a (mod p), 1<=a[0]<p (a[0]=c or p-c)
 * a[n]=a[n-1]+b[n]p^n, n>=1.
 * a[n-1]^2=a (mod p^n)
 * k=(a[n-1]^2-a)/p^n
 * k+2a[n-1]b[n]=0 (mod p), 0<=b[n]<p.
 * Then the two p-adic squareroots of a are
 * a[0]+b[1]p+b[2]p^2 + ...
 */
define padic(a,p,n){
auto i,c,t,x,pp
c=tonelli(a,p)
pp=1
print c," "
x=c
for(i=1;i<n;i++){
   pp=pp*p
   k=(x*x-a)/pp
   t=cong1(2*c,-k,p)
   x=x+t*pp
   print t," "
}
print "\n"
pp=1
c=p-c
print c," "
x=c
for(i=1;i<n;i++){
   pp=pp*p
   k=(x*x-a)/pp
   t=cong1(2*c,-k,p)
   x=x+t*pp
   print t," "
}
print "\n"
print "finished\n"
return
}
/* a=1 (mod 8)
 * a[n-1]^2=a (mod 2^(n+2)
 * a[0]=1 or 3, a[n]=a[n-1]+b[n]2^(n+1), n>=1.
 * a[0]=1=> x=1+0*2+b[1]2^2+b[2]2^3+
 * a[0]=3=> x=1+1*2+b[1]2^2+b[2]2^3+
 * k=(a[n-1]^2-a)/2^(n+2)
 * b[n]=k (mod 2), b[n]=0 or 1.
 * a[n]<2^(n+2)
 */
define twoadic(a,n){
auto i,t,x,pp,temp,k,nn
if(n<2){
  print "n<3\n"
  return
}
nn=n-1
pp=4
x=1
/*print "x:",x," "*/
print "1,0,"
for(i=1;i<nn;i++){
   k=(x*x-a)/(2*pp)
   temp=k%2
   if(temp){
     t=1
   }else{
     t=0
   }
   x=x+t*pp
   pp=pp*2
   print t,","
   /*print "x:",x,"\n"*/
}
print "\n"
pp=4
x=3
/*print "x:",x," "*/
print "1,1,"
for(i=1;i<nn;i++){
   k=(x*x-a)/(2*pp)
   temp=k%2
   if(temp){
     t=1
   }else{
     t=0
   }
   x=x+t*pp
   pp=pp*2
   print t,","
   /*print "x:",x,"\n"*/
}
print "\n"
print "finished\n"
return
}