% Octave/MATLAB functions for use with mod-2 polynomials
% represented as integers.
%
% Author: M.V.Wickerhauser
% Date: 2023-04-19
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Integer-Size Mod-2 Polynomial Degree
function degree = intmod2polydegree( p )
  degree=-1; % initialize with impossible value
  while p>0
    p = floor(p/2); % right bitshift
    degree = degree+1; % increment the degree.
  end
  return
end

% Integer-Size Mod-2 Polynomial Sums
function sum = intmod2polysum( p, q )
  sum = bitxor(p,q);
  return
end

% Integer-Size Mod-2 Polynomial Products
function prod = intmod2polyproduct( p, q )
  prod = 0;
  while p>0
    if bitand(p,1)==1  % if p is odd
      prod = bitxor(prod,q);  % prod^=q
    end
    q = q*2; % Replace q <<= 1 by its bitshift left
    p = floor(p/2); % Replace p >>= 1 by its bitshift right
  end
  return
end

% Integer-Size Mod-2 Polynomial Quotient and Remainder
function [q,r]=intmod2polydivision( p1, p2 )
  q=0; r=p1;  % initialize output
  sh = intmod2polydegree(r)-intmod2polydegree(p2); % shift
  while sh >= 0
    r = bitxor(r,p2*2^sh); % Replace r ^= (p2<<sh)
    q = bitxor(q, 2^sh); % Replace q ^= (1<<sh)
    sh = intmod2polydegree(r)-intmod2polydegree(p2); % shift
  end
 return
end


% Euclid's Algorithm For Mod-2 Polynomials
function y = intmod2polygcd(x,y)
  while  x>0
    z=x;
    [q,x]=intmod2polydivision(y,x);
    y=z; 
  end
  return
end

% Find Relatively Prime Mod-2 Polynomials of Given Degree
function polys = intmod2polyrelativeprime( p, d )
  polys=[];  % empty array to start
  dp = intmod2polydegree(p);
  if dp > 0
    qmin=2^d;
    qmax=2*qmin-1;
    for q=qmin:qmax
      if intmod2polygcd(p,q)==1
	polys=[polys q]; % append this newest discovery
      end
    end
  end
  return
end