Miller-Rabin and Primes

For those of you who do not know, Miller-Rabin is a probabilistic algorithm for testing the primality of numbers. This is different from a deterministic algorithm since with Miller-Rabin there is a change that even if the test says a number is prime that it is in fact composite. However, we can make the probability of this happening so small that we are not worried. On the other hand, if the algorithm says that a number is composite then there is no doubt that it is so.

Here is how the algorithm works. You are given a number and wish to find out if it is prime. So we choose a random integer . First we compute , if this is not 1 then we know immediately that is not prime. If this is in fact 1, we then proceed to calculate where is an odd integer. Next we calculate , if this is we choose another random integer. If it is not then we proceed with the following "cycle". Let and continue to iterate in the following manner, , until . If none of these , then is composite. But if one does satisfy this criteria then is a probable prime.

Now for the reasoning behind the algorithm. From Fermat's Little Theorem we know that where is a prime and . Using this and a few other techniques we can see that we must have that . Now if is a prime number then is a field and thus there are only 2 square roots of 1, namely 1 and negative 1. Thus if none of the is equivalent to negative 1 modulo then we have found a third square root and can immediately conclude that is not prime.

It can be shown (not it this post) that after running the algorithm with "testers" (the random integers) which all point to being prime then the probability that is composite is . Also the algorithm has runtime of where is the number of testers. It should be noted that this can be improved to if we use the fast Fourier transform to do the multiplications.

Well below is my C++ code for the Miller-Rabin algorithm.

//a plays the role of N and b is the tester
bool MR(long long a, long long b)
{
if(gcd(a,b)!=1)
return false;
unsigned long long Y;
int B=0; //a-1=M(2^B)
long long M=a-1;
while(M%2==0)
{
B++;
M=M/2;
}
Y=RS(b,M,a); //I use repeated squaring, instead of FFT, to calculate b^M
if(Y==1 || Y==a-1)
return true;
int j;
for(j between 0 and M) //this is not real code it just did this so that it would show up in blogger
{
Y=RS(Y,2,a);
if(Y==a-1)
return true;
}
return false;
}

Yes I know this looks ugly (thanks a lot blogger) but it is still readable. Below is the code for the repeated squaring function.

unsigned long long RS(long long a, long long b, long long c) // a^b mod c
{
if(b==0)
return 1;
if(b%2==0)
return (RS(a,b/2,c)*RS(a,b/2,c))%c;
if(b%2==1)
return (a*RS(a,(b-1)/2,c)*RS(a,(b-1)/2,c))%c;
}

This algorithm calculates in time.

Well if any of you are compelled to try using this here are a few cool "easy" problems you can try.
Prime Generator
Prime or Not
(Note: Using Miller-Rabin might not be the best method to solve both of these problems)

Dodged a Bullet

Well this is the fist time I have managed to avoid the "blah blah blah just friends blah blah blah" conversation with someone.

This is all attributed to my decision to become more assertive/definite when it comes to making decisions. Before I would just be indifferent about most choices when someone else asked me make a decision. It wasn't that I didn't care what we did, it was just that I did not feel comfortable calling the shots because I would feel as if I were imposing my will on them. I guess this also might explain a few other aspects of my life, which I will not divulge into on this blog. In any case, I was talking to the girl that I had a small crush on a few days ago. I had known her for a while so I knew there was a pretty good chance that I had been placed on the "shitty ladder." (some people refer to this as the friend zone) Regardless I decided to find out weather or not my intuition was correct. Since I knew that I didn't want to have the talk which was outlined at the beginning of this post I went about gathering the information in a more subtle manner. Either way I got what I was expecting but wishing would not happen. So I have given up on pursuing that relationship any further.

It was not until today that I realized just how close I had cut it. I was talking to her and she mentioned that she was going on a date with some guy. This only a few days after asking me for advice on how to tell someone she only liked them as a friend, but not hurt them. Honestly, she was asking for the impossible. It's understandable that she would not know just how unrealistic this is because she never been, and most likely will never be, in the other person's position. Well I gave her an honest answer, which she seemed to take quite well actually.

Well I am glad that this will no longer be an issue. I can finally move on and not have any regrets about what could have been. Sorry if you are reading this post and it seems that things don't like together very well, I am just writing as things pop into my head.

Until next time. I am off to do more programming.

It Has Been a While

Well the last few weeks, particularly the last week, I have been quite busy with actually school related work. Unfortunately, even though I have been busy I have not found much enjoyment through leaning any of these subjects. I think I will try and start reading Stochastic Calculus for Finance 1 again. I had stopped a while back because I found Abstract Algebra to be somewhat fascinating at the time but we all know how fads are; here one moment and gone the next. Needless to say French is still dominating my "free" time. It is quite sad how I spend more time doing work for this class than anything else. If only it were not a five credit class (the majority of my other classes are only three) I would be so much happier. You never feel satisfied when you have to decided weather to look at material for one of your major related classes or for the one class that is going to have the biggest impact on you GPA, and eighty-five percent of the time you have to side with your GPA. Thank goodness this insanity will end with the conclusion of this semester.

A few days ago we had a test in Abstract. The class is structured so that each test has two parts; a take home and in class portion. For the take home we are split into teams and have about a week to solve all of the problems. We are allowed to use any resource we can find, other than asking for help from other people outside of our teams and instructor. Thank goodness the take home part of the exam was not all that difficult, although it did make you stop and actually think about a few question. When it came time to do the in class I almost cried, I quite certain that there is no way I performed that well. The class after the exam one student was talking about how a guy with a gun was arrested in his apartment complex. To this the professor said "See compared to that the in class exam was not all the bad right?" The student's response was something along the lines of "I didn't cry after they arrested that guy, I can't however say the same thing about that exam." Well it's not going to do me much good dwelling on it now, I will just have to be more prepared for the next exams.

Managerial Economics is quite possibly the second dullest class I have taken so far (the first would most certainly have to Financial Accounting). Sure the material is interesting at times but he really doesn't have the pleasure to go into a great deal of depth on those topics. I find that he spends a lot of time explaining the basic pre-calculus math he uses in his example problems. At this point it is starting to be more of a nuisance than a point of amusement, honestly this is an intermediate level class, you should know how to do high school algebra. This paired with the fact that calculus 1 is a prerequisite for this class really bothers me. I wonder how much different, and possibly better, this class would be if he assumed you could follow the math so that he could focus on the logic behind the process. Similar to every other science and math class which assumes you understand the basic concepts from the prerequisite classes. Regardless, the majority of the assignments are not difficult if you watch the lectures and actually pay attention. We had our first test a few days ago, I didn't do as well as I had hoped but I am not that worried. I did extremely well on the free response part of the exam, it was the multiple choice part that lowered the score. This could just be me speaking as a math major but personally I prefer free response test to multiple choice test any day. With multiple choice it is either right or wrong and you have no chance to defend your position.

Not much to say about Advanced Calculus 2. We just finished the chapter on integration and I believe we are nearing the end of the chapter on uniform convergence (sequences and series of functions). Yesterday we were shown what I consider to be the most amazing thing ever, a function that is continuous everywhere but differentiable nowhere.

Showing that this is continuous for all real is pretty easy, I suppose the same could be said about showing that it is not differentiable, even thought he proof is kind of long.

After I was done with classes yesterday I went to talk to one of my professors about graduate school. During this time we discovered that there was going to be a seminar on Financial Mathematics given by another professor. I ended up attending the seminar but really did not gain too much information. Really he just gave a brief history of the topic, named some schools that offered programs in it, and concluded by listing some books for recommended reading.

Well in other nonacademic life things really haven't changed. On Tuesday I went to the gym with some friends. I didn't really do much other than cardiovascular stuff, not really a fan of weights for some reason. Walking back I was talking to a friend (the girl who I mentioned during a previous post), it was kind of interesting even though we really didn't say anything out of the ordinary. I guess it's that I really just like being around her, yes I still like her but thats a story for a different post. Anyway out of nowhere she just kind of grabs me which kind of took me by surprise. Right now I am just hoping that those few seconds will not be the best ones for this week, but the way things are going they seem to have a pretty decent chance. Finally, this week just killed my television watching. For some reason my room no longer gets Fox News, CNN, or CNN Headline News. Even though I'm not a big Fox News fan it is still better than nothing, how am I going to get my news now? Well guess I'll have to read some news papers and use the internet.

Back on My Grizzie

Well I didn't make a post about the first week of classes and there is a simple reason for that. Nothing happened!

In French that week was dedicated to reviewing material from the previous semester. Luckily we had this since over break I had forgotten some of the basic things we learned near the beginning of the year. Until Thursday I possibly had the most interesting professor. Not interesting in a positive way, she spoke French but with a Spanish accent. It wasn't bad enough that my comprehension of spoken French had drastically dropped thanks to the break but her accent certainly was not helping things (for those of you that are not aware, I took three years of Spanish in high school). Doesn't take a genius to figure that I switched into a different section as soon as one became available. The current teacher is the least organized organization freak. She prepares power point presentations for every topic we cover, and she occasionally forgets to bring them with her to class. She says the funniest things while teaching. Occasionally the projector would not work so she would need to write on the black board and would always mention how her spelling is horrendous, regardless of which language; English, French, or German, she chose to use. Getting another A in French shouldn't be too hard since she forces us to learn the vocabulary with her daily quizzes so that just leave me to learn the grammar, which is usually something trivial or close to it.

Managerial Economics is going to be a lot of work, not because of the difficulty of the material but rather because of the amount of "busy work" he is making us do. In addition to watching lectures and doing problem sets we must also read his stupid articles and post a comment. I think the worst part is that the class only meets two hours every Tuesday and Thursday. If it were my call I would choose to meet for one hour every day but Friday. That way it is a little harder to fall behind on the lectures since you don't have to watch a two hour video which requires you to set aside a good portion of your "free time". So far it looks like the only reason people have trouble with the class is because of the math. During the introductory lecture he said that he would try to use as little math as possible so it disturbs me how the math is what people find hard. They way he has chosen to teach the class requires only that one knows high school algebra and basic calculus, the class even has calculus 1 as a prerequisite. In any case getting an A in this class should not be a difficult task, just one filled with bull shit assignments.

Abstract Algebra at the moment is quite boring since we are going over basic number theory concepts. In addition to that the textbook really doesn't fit the kind of upper division books I which I prefer, the theorem-proof format. Advanced Calculus jumped right into material from the first second of class. This was expected since it is the second portion of a two semester course. We began with the proof of the generalized man value theorem (1). Currently we have just started looking at the Riemann-Stieltjes integral. These two classes, especially Abstract Algebra, should be my easiest two A's of the semester. Even though getting an A in Advanced Calculus should be easy I will continue to put a great deal of work into covering more than the professor does in our class because I wish to take the graduate level Analysis class next fall.

Of all the problems I have solved so far this semester, the following was the most pleasing, even though it was not the most difficult or interesting.

Suppose is a real, three times differentiable function on , such that
, , , and .
Prove that for some .

On nonacademic topics I have given up on someone. Since I don't feel like retyping the major argument I shall just copy it from another of my blogs.

"So I've gotten sick of being a second option. That's the main reason I've decided to say no. (I know that one person out there will know what I mean)
It all wasn't a big deal at first since I understand that sometimes emergencies happen. But the rate at which these "emergencies" occurred you start to wonder how many are real emergencies and how many are people bitching and moaning and not knowing how to handle their own "problems". Either way eventually you feel like you're always at the bottom of their list, even when you had a previously planned engagement.
Well I guess the last two days are what really did it for me. For starters the conversation we had wasn't the most comfortable thing for me, and I'm not referring to the portion about periods. I am honestly starting to believe that no good deed goes unpunished. Today you call of something we planned because you didn't realize that trying to do all your homework in the few hours u would be home on Monday really wasn't going to work. Guess you should have realized that before we made plans. However, I probably would not have been as ticked about this if I was informed before wasting 3-4 hours of my day waiting for you to cancel at the last minuet.
Either way I'm saying fuck it. I am no longer going to go out of my way just to be with you if it's obviously not as important to you. Maybe you will notice, maybe you won't, either way I'm better off since I'll be with people who want my company just as much as I want theirs."

As previously stated this is one of the two main reasons I have decided to no longer "pursue" her. Currently not many people know about this so worst case scenario is that we remain friends. Some of you might say that I am being selfish but here is my opinion on the matter. Always make number one first in your life. Until someone gets to the point where they have earned the number one status thats how it will be. Don't get me wrong I give people many opportunities to earn that status, the girl in the above section had probational number one status, but as you can clearly see that is no longer the case. Currently I can think of one person who is around 1.2 status, so attaining that precious number one spot is possible even for mortal women.
-------------------------------------------------------------------------------------------------
(1) Let and be continuous real-valued functions on and differentiable on . Then there exist a point such that . (2)

(2) Now some of you might think that Rolle's theorem is just a special case of the mean value theorem, but it turns out that Rolle's theorem is an essential tool for proving this theorem.

Convexity and Continuity

Not to disappoint I shall at least make one new post during my winter break. However, do not look for this to be a recap of how things went. If I could I would rather just forget that these three weeks or so ever happened. On the bright side I did however, manage to get some productive things done. I finished reading the chapter on continuity and have almost finished reading the chapter on differentiation. While working through the continuity exercised I ran into one that was particularly interesting problem. Before going any further I would like to mention that I had to ask for help in finding this solution.

Theorem:
Every real-valued convex function is continuous.

A real-valued function

defined in is said to be convex if



whenever and .

Lemma: If is continuous in (a,b) and if then



Proof of lemma: This is not to difficult to prove so I shall just give the major idea and leave the rest to the reader. Let . Obviously , so use this new way to express and the rest follows with ease.

Proof of theorem:

First we choose a point

and a neighborhood of such that . Now using the lemma we have that

, for .

Now from this we see that there is a positive number such that . Let . Thus if we have that .