2
\$\begingroup\$

I have posted a discussion on Math.SE regarding visualizing the complex space and effects of factorization methods on that space. A quick link to the paper is available here. I have 3 routines in that paper, the first is the complex space generator. It works, but it is very slow and would appreciate any suggestions on improvement.

Complex Space Generator:

Complex.Space.Generator <- function(N){
  min.real = ceiling(sqrt(N))
  segtop_x = ceiling(N/6)+1
  segtop_y = floor(N/6)-1
  plot(N,N,xlim=c((0),N/3), ylim =c((0),N/6),xlab="Real",ylab="Imaginary")
  segments(3,0,segtop_x,segtop_y)
  segments(segtop_x,segtop_y,N/3,0, lty = "dotted")

  for (i in 3:N/3){
    for (j in 0:N/3){
      i=as.integer(i)
      j=as.integer(j)
      if((i-j)>=3 && (i+j)<=(N/3) && (i-j)<=min.real)
        points(i,j, pch = 17,col = ifelse((i-j)*(i+j) < N,'blue',ifelse((i-j)*(i+j) == N,'green','red')))
    }
  }
}

The second routine is the simultaneous factorization method involving Fermat and trial division. It is pretty fast, but I'm sure some improvements can be identified.

 Simultaneous.Complex.Factorization <- function(N){
 min.real = ceiling(sqrt(N))
 max.imaginary = min.real - 3
 divisor = min.real + max.imaginary ### 135degree yellow line
 ### Estimate of where complex space turns red
 min.imaginary = floor(mean(c((N/divisor),max.imaginary)))
 ### Corresponding real to above estimate
 max.real = divisor - min.imaginary
 j = 0L
 while (j>=0L ){
     if(
      sqrt(((min.real + j)^2) - N)%%1==0 |   ### Vertical Fermat

      sqrt(((max.imaginary - j)^2) + N)%%1==0 |    ### Horizontal Fermat

      (N/((min.real+j)-(max.imaginary-j)))%%1==0 |    ### Trial Division

      sqrt(((max.real - j)^2) - N)%%1==0 |    ### Vertical Fermat from estimate

      (N/((max.real-j)-(min.imaginary+j)))%%1==0    ### Trial Division from estimate
      ) {

return(as.matrix(c(iterations=j,
     mapped.real = (min.real+j)-(max.imaginary - j),
     Factor_v = if((sqrt((min.real+j)^2 - N))%%1==0) (min.real+j)-sqrt((min.real+j)^2 - N),
     Factor_h = if((sqrt((max.imaginary - j)^2 + N))%%1==0) (max.imaginary - j) + sqrt((max.imaginary - j)^2 + N),
     Factor_td = if((N/((min.real+j)-(max.imaginary-j)))%%1==0) (N/((min.real+j)-(max.imaginary-j))),
     Factor_v.2 = if((sqrt((max.real-j)^2 - N))%%1==0) (max.real-j)-sqrt((max.real-j)^2 - N),
     Factor_td.2 = if((N/((max.real-j)-(min.imaginary+j)))%%1==0) (N/((max.real-j)-(min.imaginary+j)))
     )))}

 j = j + 1L

  }
}

And finally I have the alternative method presented in the paper. It is very slow compared to the above method even though it requires noticeably less iterations.

Viole.Factorization <- function(N){
 min.real = ceiling(sqrt(N))
 max.imgainary = (N-9)/6
 iterated.average = 0L

 for (i in 2:log2(max.imgainary)){
      iterated.average[1] = mean(c(min.real,N))
      iterated.average[i] = mean(c(iterated.average[i-1],N))
      }

 descending.iterations = floor(iterated.average)
 ascending.iterations = ceiling(iterated.average)
 print(iterated.average)
 j = 0L

 while(j>=0L){
      for(i in 1:length(iterated.average)){
      if( (descending.iterations[i]-j > descending.iterations[i-1] | ascending.iterations[i]+j < ascending.iterations[i+1]) &&
      GCD(descending.iterations[i]-j,N)>1 && GCD(descending.iterations[i]-j,N)<N |
      GCD(ascending.iterations[i]+j,N)>1 && GCD(ascending.iterations[i]+j,N)<N
      ){

 return(c("Factor"=GCD(descending.iterations[i]-j,N),"Factor"=GCD(ascending.iterations[i]+j,N),"Iterated.Average.Level"=i,"Iterations"=j))}
      }
 j = j + 1L
 }
}

I look forward to any insights regarding the routines. If you have any suggestions or questions on the content of the paper then please comment on the Math.SE discussion.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.