Do you have to be a permanent resident or special permanent resident to naturalize?

Surprisingly, the answer is NO.

The only mention of 在留資格 {zairyū shikaku} (status of residence, or visa status) in the official 帰化の条件 {kika no jōken} (criteria for naturalization) falls under 住所条件 {jūsho jōken} (address requirement), which states:

帰化の申請をする時まで， {kika no shinsei o suru toki made,}引き続き５年以上日本に住んでいることが必要です。 {hikitsuzuki gonen ijō nihon ni sundeiru koto ga hitsuyō desu.}
なお，住所は，適法なものでなければなりませんので， {nao, jyūsho wa, tekihō na mono denakereba narimasen node,}正当な在留資格を有していなければなりません。 {seitō na zairyū shikaku wo yūshiteinakereba narimasen.}

Loosely translated: The applicant must have lived in Japan for five years continuously leading up to the time of application. Furthermore, because the address must be a legitimate one, the applicant must hold a valid status of residence.

A valid status of residence - that's it. And the five-year requirement is shortened to one or three years (depending on whether or not you were married or adopted for three years or more before coming to Japan) for spouses or children of Japanese nationals. No mention of 永住権 {eijūken} (permanent residency) is ever made.

If you need further proof, I naturalized straight from a three-year spouse visa, never even applying for permanent residency. Of course, if you do have permanent residency, it's probably one more point in your favor when your application is being reviewed. But no, it's not a requirement at all.