地雷原でタップダンスするかのようなご質問ありがとうございます。この分野は間違えると八方から斧が飛んでくるので慎重に答えたいと思います。

素因数分解と言っているので今回はRSA暗号に絞った話をしていると見受けられます。公開鍵で暗号化して秘密鍵で復号（復号化は誤用です）する際の算術的な概要は以下の通りです（実は僕は素因数分解をイメージしてもよくわからないのですが…）。

平文xを公開鍵(e, N)で暗号化して暗号文yを得る

y = x ^ e mod N

暗号文yを秘密鍵(d, N)で復号して平文xが戻ってくる

x = y ^ d mod N

つまりRSA暗号は原理的には

x = x ^ (e*d) mod N

が常に成立する事に基づいた方法です。ここまでは質問者様も理解している事と思います。本題は

秘密鍵で暗号化して公開鍵で復号化するという部分の理屈

ですが実はRSAでの署名も同じで「公開鍵で暗号化して秘密鍵で復号する」というのが正しいです。署名対象の平文に対して秘密鍵で復号処理をかける事を署名と呼ぶのがポイントです。平文と呼んでいる物は厳密にはハッシュ値なのですがRSAの理解とは独立であり上の文との対称性を明白にするため敢えて平文と書きます。

平文xを秘密鍵(d, N)で復号して署名zを得る

z = x ^ d mod N

署名zを公開鍵(e, N)で暗号化すると平文xが戻ってくる

x = z ^ e mod N

こちらも原理的には

x = x ^ (d*e) mod N

が常に成立することに基づいています。

「復号」という単語は国語的に考えたら「元の値に戻す処理」であり、平文に対してこれを行う事は国語的に変なのですが、算術的には一貫して「d乗してmod Nする」という操作です。

同様に「暗号化」という単語 も国語的に考えたらその出力は人間に読めない物になりそうですがRSA署名の文脈では暗号化した結果の出力こそが平文で、算術的には一貫して「e乗してmod Nする」という操作です。

つまりRSAにおける暗号と署名はe乗とd乗をどっちに先にやるかという違いでしかなく、先に復号を行ってもその後で暗号化を行えば元に戻ってくる特性があるのがRSAです。ですので「公開鍵で暗号化して秘密鍵で復号する」を理解していれば充分で、逆順の「秘密鍵で復号して公開鍵で暗号化する」の順で処理しても元の値に戻ってくるのは数式をよく見れば難しい話ではありません。質問にある「反対の場合の理屈」というのも強いて言うなら乗算の交換法則です。

平文に対して復号という言葉を使うのはやはり誤解を招きがちなのでRSA署名の文脈では「秘密鍵で復号」の事を「秘密鍵で署名」と呼ぶほうが一般的です。

なおこの返答の最も重要な点は、この特性はRSA暗号に限った話であって、社会で使われている楕円曲線暗号等では全く勝手が違いますので適宜注意深くテキストを読んでください。