% This script finds the primitive polynomials of order 8 mod 9. % It does this by finding the polynomials who have order 9^8-1 % % WARNING: No primitive polynomials exist for the module described above. % % Claim: For the module (think field but over a ring) GM(9^8), now referred % to as M, which is the splitting module of 8th order polynomials with % coefficients of Z/9Z, there exist no shift register generators. % % A shift register generator is basically a polynomial in M that is % primitive. The coefficients of a primitive polynomial's powers are % used to shift the sequence. This shift has specific properties due % to the properties of primitive polynomials. Pseudonoise sequences % are sequences that result from this. % A primitive polynomial, p, is defined by the fact that if it has a % root R, the linear span of {1, R, R^2,..,R^8} is M. A concequence of % this is the fact that every element of M can be written as a powers % (this contains linear combinations of p as well) of p. An additional % concequence of this is the fact that the order of p must equal the % order of the module, 9^8-1. % But there exist noninvertible elements in M, due to it being a module % (think 3x3=0 so 3xq cannot =1 in any case), no such p exists because: % % For each q in M, q=p^n for some n in Z and <9^8-1. The order of M is % 9^8-1, therefore p^9^8-1=1. Therefore there exists a b st b=p^m with % m=9^8-1-n, and qb=1. This contradicts the fact that there are % noninvertible elements in M. % % Therefore, there exist no primitive polynomials in M, the splitting % module of 8th order polynomials with coefficients in Z/9Z. sprintf('No primitive polynomials exist for the splitting module GM(9^8),') sprintf('which is the module of 8th order polynomials with coefficients in Z/9Z') error 'Read message' % Previous Code % % order=9^8-1; % order1=order-1; % eq=zeros(order,9); % coefs=zeros(order,1); % res=ones(order1,1); % fid=fopen('/jet/kerr/class/mseq/primpolys9','w'); % % for a=0:8 % for b=0:8 % for c=0:8 % for d=0:8 % for e=0:8 % for f=0:8 % for g=0:8 % for h=0:8 % for i=0:8 % p=[a b c d e f g h i]; % for o=1:order % % Alternate way without if % % po(1,:)=polypow(p,o) % if o==1 % po=zeros(1,17); % po(1,:)=conv(p,p); % else % po(1,:)=conv(p,pos); % end % for pow=1:8 % po(1,pow+9)=po(1,pow+9)+po(pow); % po(1,pow)=0; % end % po=mod(po,9); % pos=zeros(1,9); % for pows=1:9 % pos(1,pows)=po(1,8+pows); % end % clear pows pow % eq(o,:)=pos; % end % clear o % coefs(:,1)=sum(abs(eq')); % for n=1:order1 % if coefs(n,1)>0 % res(n,1)=0; % else % res(n,1)=99999; % end % end % clear coefs eq % if sum(res)==0 % fprintf(fid,' %d', p); % fprintf(fid,'\n'); % p % end % clear res % end % end % end % end % end % end % end % sprintf('Done a 7th degree') % end % sprintf('Done a 8th degree') % end