c RSA1.f
c May 30 2008
c Given e, n, find best approx to n of form e*x lying under n

	implicit integer(a-z)
	integer*1 na(1000),ni(1000),ans(10000)

	M=5000
	len=20
	e=9
	write(*,*)"RSA1.f, e, M = ",e,M

	do 10 n=0,M
	call binexp(n,na,len,nwt)
	dist=1000000
	do 11 i=0,n/e
	t1=i*e
	call binexp(t1,ni,len,nwt)
	call ischild(na,len,ni,len,wt)
	if (wt.lt.0)goto 11
	if (wt.ge.dist)  goto 12
	dist=wt
	at=i
12	continue
11	continue
	write(*,104)n,dist,at
	ans(n)=dist
10	continue
300	continue
	write(*,102)(ans(i),i=0,M)
98	format(60i1)
99	format(6i4)
100	format(60i1)
102	format(15i4)
104	format(3i12)

cc test ischild
c	n=9
c	len=20
c	call binexp(n,na,len,nwt)
c	do 2 i=0,16
c	call binexp(i,ni,len,nwt)
c	call ischild(na,len,ni,len,j)
c	write(*,99)n,i,j
c2	continue


cc test bin expansion
c	do 1 n=0,8
c	len=8
c	call binexp(n,na,len,nwt)
c	write(*,*)"n = ",n
c	write(*,98)(na(iii),iii=1,len)
c	write(*,*)"nwt = ", nwt
c1	continue
	stop
	end
	
c is k a child of n?
c if so 
	subroutine ischild(na,lenn,nk,lenk,nwt)
	implicit integer(a-z)
	integer*1 na(1000),nk(1000)
	l=min(lenn,lenk)
	nwt=0
	do 10 i=1,l
	if(na(i).eq.0.and.nk(i).eq.0)goto 10
	if(na(i).eq.1.and.nk(i).eq.0)goto 100
	if(na(i).eq.0.and.nk(i).eq.1)goto 101
	if(na(i).eq.1.and.nk(i).eq.1)goto 10
101	continue
	nwt=-1
	goto 20
100	continue
	nwt=nwt+1
10	continue
	do 30 i=l+1,lenn
	nwt=nwt+na(i)
30	continue
20	continue
	return
	end

c get bin expansion of number
	subroutine binexp(n,na,len,nwt)
c n = input
c na = array for bin expansion
c len = dim of na
c nwt = binary wt of n
	integer*1 na(1000)
	nwt=0
	do 10 i=1,len
10	na(i)=0
	i1=n
	do 20 i=1,len
c temp
c	write(*,*)"i1 = ",i1
c temp
c	write(*,100)(na(iii),iii=1,len)
	if(i1.eq.0)RETURN
	j=mod(i1,2)
	i1=(i1-j)/2
	nwt=nwt+j
	na(i)=j
20	continue
	if(i1.ne.0)write(*,*)"ERROR in binexp at n = ",n
	RETURN
100	format(60i1)
99	format(6i4)
	end